ACM-ICPC 2018 南京赛区网络预赛
ACM-ICPC 2018 南京赛区网络预赛
- 全程被学长带飞
A. An Olympian Math Problem
题目描述
S(n) = 1 1 ! + 2 2! + 3 3! + … + (n-1) (n-1)!
给定n，求S(n) % n
分析
高中数学题。
观察式子可得，k * k! = (k+1)! - (k)!
所以S(n) = 2! - 1! + 3! - 2! + … + n! - (n-1)! = (n! - 1) % n = n-1
所以输出n-1即可
代码
#include<iostream>
using namespace std;
typedef long long LL;
int main()
{
int kase;
LL n;
cin >> kase;
while(kase--)
{
cin >> n;
cout << n-1 << endl;
}
}
E. AC Challenge
题目描述
有n道题(n <= 20)，每个题目都拥有一个分数a和一个分数b。每道题都有s个它的前置题目，你必须把前置题目做完才能做这道题。
每分钟可以做一题，在第t分钟做的题获得的分数为a * t + b
每道题都可以选择做或者不做，求一种做题方案，使得获得的分数最高
分析
个人感觉属于很基础的状压DP，我之前都没怎么碰过这类题。
由于每道题的a和b可能是负数，很显然如果a和b都是负分的话这题就不用做了。换句话说，最差得分也是0分，不可能是负分。
考虑到n的范围非常小，我们可以从n入手。考虑状压dp，我们将每道题的做题情况看作二进制下的0和1。比如00110110就代表做了2,3,5,6这四道题的状态。
枚举每一个状态，既然我们已经知道了当前状态的做题情况，我们也就知道了当前状态经过的分钟数t。对于每一个状态，它都是通过一个前置状态多做一题而转移的，比如011010这个状态可以通过011000,010010,001010这三个状态转移而来。易得转移方程dp[k] = max(dp[i]) i为前置状态
在考虑一个状态的前置状态时， 要注意是否满足做这道题的条件。
代码
//状压DP
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int MAXN = (1<<20) + 10;
const int maxn = 30;
int ans,n,dp[MAXN];
struct Pro //记录每个题目的a,b与前置题目要求
{
int a,b,s;
LL state;
}pro[maxn];
int get_time(int s) //获得一个状态的时间
{
int t = 0;
while(s > 0)
{
if(s&1) t++;
s >>= 1;
}
return t;
}
void input(int k)
{
scanf("%d%d%d",&pro[k].a,&pro[k].b,&pro[k].s);
if(pro[k].s > 0)
{
int p;
for(int i=0;i<pro[k].s;i++)
{
scanf("%d",&p);
pro[k].state |= (1 << (p-1));
}
}
}
void solve()
{
ans = 0;
dp[0] = 0;
for(int i=1;i<(1<<n);i++) //枚举每一种状态
{
int tt = get_time(i);
//cout << tt << endl;
for(int j=0;j<n;j++) //枚举每个状态的前置状态
{
if(i & (1<<j)) //
{
int tmp = i ^ (1<<j);
if((i & pro[j].state) == pro[j].state) //判断是否满足条件，若满足则更新状态
{
dp[i] = max(dp[i],dp[tmp] + tt * pro[j].a + pro[j].b);
//cout << dp[i] << endl;
}
}
ans = max(ans,dp[i]);
}
}
}
int main()
{
memset(dp,-0x3f,sizeof(dp));
scanf("%d",&n);
for(int i=0;i<n;i++)
input(i);
solve();
printf("%d\n",ans);
}
J. Sum
题目描述
对于一个数num，我们可以把它分解成p(m) m + p(n) n + p(k) k的形式。
若一个数的所有质因数的指数都小于2，我们称之为square-free number。
比如6 = 2 3 ,6是一个square-free number
而8 = 2 2 2,所以8不是
设函数f(n)，表示n可以拆分为两个square-free number a 和 b的乘积形式的方案数
比如6可以拆分为 1 6 , 6 1 , 2 3 , 3 2，所以f(6) = 4
对于给定n，求f(1) + f(2) + f(3) + … + f(n)
题目分析
这题有点需要思维..
首先可以发现，对于素数k,f(k) = 2
如果一个数k的一个质因子的指数大于2，则f(k) = 0
如果一个数k的一个质因子p的指数为1,则f(k) = 2 f(k / p) , 因为将k/p分解成a b的形式后，p可以放在a或者b上，贡献为2
如果一个数k的一个质因子p的指数为2,则f(k) = f(k/p/p) , 因为k/p/p分解后，将两个p分别放在a和b上，无贡献
暴力做的话，需要枚举每一个数的质因子，然后看每个质因子的指数，肯定要超时。
我们可以只考虑最小质因子，通过递推的方式在O(n)下解决问题。因为欧拉筛可以筛出每一个数的最小质因子，所以我们先进行一遍欧拉筛，然后通过计算最小质因子的指数来递推
代码
//欧拉筛
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 2e7;
int tot,prime[maxn+10],f[maxn+10],summ[maxn+10],min_prime[maxn+10];
void Euler()
{
for(int i=2;i<=maxn;i++)
{
if(!min_prime[i]) //如果没有找到素因子，那么它本身就是素数
{
prime[tot++] = i;
min_prime[i] = i;
}
for(int j=0;j<tot && prime[j] * i <= maxn;j++)
{
min_prime[prime[j] * i] = prime[j];
if(!(i % prime[j])) break;
}
}
}
void solve()
{
f[1] = 1;
for(int i=2;i<=maxn;i++)
{
int p = min_prime[i];
if(i == p) f[i] = 2;
else
{
if(i % (p * p * p) == 0) f[i] = 0;
else if(i % (p * p) == 0) f[i] = f[i / p / p];
else f[i] = 2 * f[i / p];
}
}
summ[1] = f[1];
for(int i=2;i<=maxn;i++) summ[i] = summ[i-1] + f[i];
}
int main()
{
Euler();
//for(int i=1;i<=20;i++) cout << min_prime[i] << endl;
solve();
int kase,n;
cin >> kase;
while(kase--)
{
cin >> n;
cout << summ[n] << endl;
}
}
L. Magical Girl Haze
题目描述
给出一个有向图，有n个节点m条边，现在你可以将最多k条边的长度变为0。求1到n的最短路
分析
看起来很复杂，实际上非常简单。
构造k层这样的图，如果节点u和v连通，那么就连通当前层的u–>v,并将当前层的u和上一层的v连通，将权值设为0
太巧妙了。
注意spfa会被卡，这道题要用dijkstra + heap
代码
//dij堆优化？
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int maxn = 5e6 + 10;
const int inf = 0x3f3f3f3f;
typedef long long LL;
int n,m,k,cnt,head[maxn],vis[maxn];
LL d[maxn];
struct Edge
{
int next;
int to;
int dis;
}edge[maxn];
struct Node
{
int to;
LL dis;
bool operator < (const Node &a) const
{
return dis > a.dis;
}
};
void add_edge(int a,int b,int d)
{
edge[cnt].next = head[a];
edge[cnt].to = b;
edge[cnt].dis = d;
head[a] = cnt++;
}
void dijkstra()
{
priority_queue<Node> pq;
d[1] = 0;
pq.push(Node{1,0});
while(!pq.empty())
{
Node t = pq.top();pq.pop();
vis[t.to] = 1;
for(int i=head[t.to];i!=-1;i=edge[i].next)
{
int next = edge[i].to;
LL dis = edge[i].dis;
if(vis[next]) continue;
if(d[next] > d[t.to] + dis)
{
d[next] = d[t.to] + dis;
pq.push(Node{next,d[next]});
}
}
}
}
void init()
{
cnt = 0;
memset(d,inf,sizeof(d));
memset(vis,0,sizeof(vis));
memset(head,-1,sizeof(head));
}
int main()
{
int kase,a,b,c;
scanf("%d",&kase);
while(kase--)
{
scanf("%d%d%d",&n,&m,&k);
init();
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&a,&b,&c);
for(int j=0;j<=k;j++)
{
add_edge(a+j*n,b+j*n,c);
if(j != k) add_edge(a+j*n,b+(j+1)*n,0);
}
}
dijkstra();
LL ans = inf;
for(int i=0;i<=k;i++) ans = min(ans,d[n+i*n]);
printf("%lld\n",ans);
}
return 0;
}
这里要关注一下手撸简易链表的操作
int head[maxn];
struct Edge
{
int next;
int to;
int dis;
}edge[maxn];
void add_edge(int a,int b,int d)
{
edge[cnt].next = head[a];
edge[cnt].to = b;
edge[cnt].dis = d;
head[a] = cnt++;
}
不太好描述…理解一下吧