网站建设商品的分类,动效做的好的网站,h5生成小程序,常用的搜索引擎Wannafly 挑战赛27
题目连接
https://www.nowcoder.com/acm/contest/215#question A.灰魔法师
题目 题解
考虑到可能的完全平方数只有400400400多个,因此对于每种数,直接暴力枚举所有的完全平方数计算一下就可以了.
代码
#include iostream
#define int long lon…Wannafly 挑战赛27
题目连接
https://www.nowcoder.com/acm/contest/215#question A.灰魔法师
题目 题解
考虑到可能的完全平方数只有400400400多个,因此对于每种数,直接暴力枚举所有的完全平方数计算一下就可以了.
代码
#include iostream
#define int long long
const int N 100007;
int a[N];
int n;
int p2[N];
int tot;
signed main() {for(int i 1;;i) {int a i*i;if(a 2*N) break;p2[tot] a;}std::cin n;for(int i 1;i n;i) {int tmp;std::cin tmp;a[tmp] ;}int ans 0;for(int i 1;i 100000;i) {if(a[i] 0) continue;for(int j 0;j tot;j) {int an p2[j] - i;if(an i) continue;if(an i) ans a[i]*(a[i]-1)/2;else if(an 100000)ans a[i]*a[an];}}std::cout ans std::endl;
}B.紫魔法师
题目 题解
注意到至少当存在一个奇环的情况下,一定需要333种颜色,而其他情况下只要222种颜色就足够了.
只需要用tarjan算法求其点双连通分量的大小即可.
代码
#include iostream
#include algorithm
#include cstring
#include stack
#include vector
#define pr(x) std::cout #x : x std::endl
#define rep(i,a,b) for(int i a;i b;i)
const int N 100007;
struct edge{int u,v,nxt;
}es[N2];
int head[N],cnt;
int vis[N],dfn[N],low[N],idx;
int v[N1],u[N1];
std::stackint stk;
void addedge(int u,int v) {es[cnt].u u;es[cnt].v v;es[cnt].nxt head[u];head[u] cnt;
}
int flag;
void tarjan(int u,int fa) {dfn[u] low[u] idx;vis[u] 1;for(int e head[u];e ! -1;e es[e].nxt) {int v es[e].v;if(v fa) continue;stk.push(e);if(!vis[v]) {tarjan(v,u);if(low[u] low[v]) low[u] low[v];if(dfn[u] low[v]) {//割点int cnt 0;while(true) {int se stk.top();stk.pop();cnt;if(se e) break;}if(cnt 1 cnt % 2 ! 0) {flag 1;}}}else low[u] std::min(low[u],dfn[v]);}
}
int n,m;
int main() {memset(head,-1,sizeof(head));std::ios::sync_with_stdio(false);std::cin n m;rep(i,1,m) {int u,v;std::cin u v;addedge(u,v);addedge(v,u);}tarjan(1,0);if(flag) std::cout 3 std::endl;else std::cout 2 std::endl;return 0;
}C.蓝膜法师
题目 题解
树形dp
状态定义
定义dp[u][i]dp[u][i]dp[u][i]表示uuu子树中包含节点uuu的连通块大小为iii,且其余联通块大小均≤k\le k≤k的方案数.
注意上述定义中dp[u][0]dp[u][0]dp[u][0]是没有意义的,我们再定义dp[u][0]∑t1min{size[u],k}dp[u][t]dp[u][0] \sum_{t 1}^{min\{size[u],k\}} dp[u][t]dp[u][0]∑t1min{size[u],k}dp[u][t].
转移方程的计算:
当我们要计算子树uuu的dpdpdp值的时候,其儿子节点分别为v1,v2,...,vmv_1,v_2,...,v_mv1,v2,...,vm.
如果我们将通向儿子节点vvv的某条边切断,那么这个儿子对uuu节点联通块大小的贡献就没了,但是它的方案数可以取dp[v][1..k]dp[v][1..k]dp[v][1..k],这也就是我们定义dp[v][0]dp[v][0]dp[v][0]的意义所在了,很巧妙地,dp[v][0]dp[v][0]dp[v][0]就刚好等于儿子vvv对uuu的联通块贡献为000时的方案数.
那么方程就得到了
dp[u][i]∑t1t2...tmi−1dp[v1][t1]∗dp[v2][t2]∗...∗dp[vm][tm]dp[u][i] \sum_{t_1t_2...t_mi-1}dp[v_1][t_1]*dp[v_2][t_2]*...*dp[v_m][t_m]dp[u][i]∑t1t2...tmi−1dp[v1][t1]∗dp[v2][t2]∗...∗dp[vm][tm]
最后答案就是dp[1][0]dp[1][0]dp[1][0]
实现方式
我们可以先将v1v_1v1与uuu合并,再将v2v_2v2与uuu合并…
代码
#include iostream
#include vector
#include cstring
#include algorithm
const int N 2018;
typedef long long LL;
const LL P 998244353;
std::vectorint edge[N];
LL dp[N][N];
LL tmp[N];
int sz[N];
int n,k;
void dfs(int u,int fa) {sz[u] 1;dp[u][1] 1;for(int v : edge[u]) {if(v fa) continue;dfs(v,u);memset(tmp,0,sizeof(tmp));for(int i 1;i sz[u];i) {for(int j 0;j sz[v] i j k;j) {tmp[ij] (tmp[ij] (dp[u][i] * dp[v][j] % P)) % P;}}for(int i 1;i k;i)dp[u][i] tmp[i];sz[u] sz[v];}for(int i 1;i k;i)dp[u][0] (dp[u][0] dp[u][i]) % P;
}
int main () {std::ios::sync_with_stdio(false);std::cin n k;for(int i 0;i n-1;i) {int u,v;std::cin u v;edge[u].push_back(v);edge[v].push_back(u);}dfs(1,0);std::cout dp[1][0] std::endl;return 0;
}D.绿膜法师
题目 题解
对于刚加入的数xxx来说,它与集合中其它的数字的gcdgcdgcd必然是它的约数. 那么枚举xxx的约数ddd,其它的数如果与xxx的gcddgcd dgcdd的话,那么其它的数必然也要有约数ddd.因此我们考虑维护一个数组muls[i]muls[i]muls[i],表示集合中的数是iii的倍数的有多少个数.
从大到小枚举xxx的约数ddd,然后muls[d]muls[d]muls[d]就表示与xxx的gcddgcddgcdd的数的个数.随后枚举ddd的约数d2d_2d2,并muls[d2]−muls[d]muls[d2]-muls[d]muls[d2]−muls[d],这样的话就保证了刚刚用过的数不会重复使用(相当于容斥一下,倒序dpdpdp的感觉).依次类推,注意删掉的数在下一个数加入集合之前要加回来,恢复现场.
100000100000100000内的数最多有128128128个约数. 每个数的约数的约数个数和最大不超过2835每个数的约数的约数个数和最大不超过2835每个数的约数的约数个数和最大不超过2835 时间复杂度不会超过100000∗28353e8100000*28353e8100000∗28353e8.总之O(能过)O(能过)O(能过).
代码
#include iostream
#include algorithm
#include vector
#include cstring
#include stack
#include queue
#define pr(x) std::cout #x : x std::endl
#define rep(i,a,b) for(int i a;i b;i)
typedef long long LL;
const int N 100007;
std::vectorint ds[N];
LL mod_pow(LL x,LL n,LL p) {LL res 1;while(n) {if(n1) res res * x % p;x x * x % p;n 1;}return res;
}
void sieve() {for(int i 1;i 100000;i) {for(int j 1;j*j i;j) {if(i % j ! 0) continue;ds[i].push_back(j);if(j*j ! i) ds[i].push_back(i/j);}std::sort(ds[i].begin(),ds[i].end(),[](int a,int b){return a b;});}
}
LL muls[N];
int n;
int main() {sieve();std::ios::sync_with_stdio(false);std::cin n;while(n--) {LL x,k,p;std::cin x k p;for(auto t : ds[x]) muls[t] ;LL ans 0;std::queueint Q;for(auto t : ds[x]) {ans (ans muls[t]*mod_pow(t,k,p)) % p;int tmp muls[t];Q.push(tmp);for(auto ft : ds[t]) {muls[ft] - tmp;}}for(auto t : ds[x]) {int tmp Q.front();Q.pop();for(auto ft : ds[t])muls[ft] tmp;}std::cout ans std::endl;}return 0;
}
