| ID | Origin | Title | ||
|---|---|---|---|---|
 | / | Problem A | ||
| / | Problem B | ||
| Problem C | ||||
| / | Problem D | |||
| Problem E | ||||
| Problem F | ||||
| / | Problem G | ||
| / | Problem H | ||
| / | Problem I |
A.
d.找出不同的数。。
#include#include using namespace std;int main(){ int T; int N; int ID[128]; int i; int sum1,sum2; int p1,p2; scanf("%d",&T); while(T--){ scanf("%d",&N); for(i=0;i
B.
d.手机滑屏解锁的问题，给出几个1~9之间的几个数，求出密码的所有可能。
s.dfs
#include#include #include using namespace std;bool exist[16];bool vis[16];int can[16][16];int t_path[212345][10];int path[16];int n;int sum;void dfs(int u,int now){ int i; if(now>n){ for(i=1;i<=9;++i){ t_path[sum][i]=path[i]; } ++sum; return; } for(i=1;i<=9;++i){ if(exist[i]&&!vis[i]){ if( (u==1&&(i==3||i==9||i==7)) || (u==3&&(i==1||i==7||i==9)) || (u==9&&(i==7||i==1||i==3)) || (u==7&&(i==9||i==3||i==1)) ){ if(vis[can[u][i]]){ path[now]=i; vis[i]=true; dfs(i,now+1); vis[i]=false; } else{ } } else if( (u==2&&i==8) || (u==8&&i==2) || (u==4&&i==6) || (u==6&&i==4) ){ if(vis[can[u][i]]){ path[now]=i; vis[i]=true; dfs(i,now+1); vis[i]=false; } else{ } } else{ path[now]=i; vis[i]=true; dfs(i,now+1); vis[i]=false; } } }}void init(){ memset(exist,false,sizeof(exist));}int main(){ memset(can,0,sizeof(can)); can[1][3]=2; can[1][9]=5; can[1][7]=4; can[3][1]=2; can[3][7]=5; can[3][9]=6; can[9][7]=8; can[9][1]=5; can[9][3]=6; can[7][9]=8; can[7][3]=5; can[7][1]=4; //--- can[2][8]=5; can[8][2]=5; can[4][6]=5; can[6][4]=5; int T; int i; int t; int j; scanf("%d",&T); while(T--){ scanf("%d",&n); init(); for(i=0;i
C.
d.线段相交拆分问题
s.先排序，好像还可以。。
D.
E.
d.黑白图像的问题
ps:好像用连通块来判断，还有黑白点的比例。题目比较长，没读题。
F.
G.
d.积分求体积，求面积。
#include#include #include using namespace std;#define PI M_PIint main(){ int T; double r,h,d,v,s; scanf("%d",&T); while(T--) { scanf("%lf%lf%lf",&r,&h,&d); v=h*PI*(r+d)*(r+d)+PI*r*r*d*2+2*2*PI*(1.0/3*d*d*d+d*d/4*PI*r); s=2*(PI*r*r+PI*(r+d)*h+2*PI*d*d+PI*PI*r*d); printf("%.12f %.12f\n",v,s); } return 0;}
H.
d.炉石传说也来水题了。。
#include#include using namespace std;int main(){ int T; int A1,H1; int A2,H2; int H3,H4; scanf("%d",&T); while(T--){ scanf("%d%d%d%d",&A1,&H1,&A2,&H2); if(A1==0){ printf("Invalid\n"); continue; } H3=H1-A2; H4=H2-A1; if(H3<=0){ printf("Discard "); } else{ printf("%d %d ",A1,H3); } if(H4<=0){ printf("Discard\n"); } else{ printf("%d %d\n",A2,H4); } } return 0;}
I.
ps:又是最大公约数的问题，尴尬。。
d.给出n和k, 求出n个数的任意非空子集的最大公约数的k次方的期望, 最后求出期望*(2^n-1)
s.容斥原理
每取一个子集的概率都为 1/(2^n-1), 结果除以(2^n-1),则实际上是求出每个非空子集的k次方的和.
题目转化为gcd为i的子集为多少, 枚举i 从MAX到1.
对于每个i, 求出n个数中为i 的倍数为cnt个,
则gcd=i 的非空子集的个数dp[i] = (2^cnt-1) - dp[j] (j为i 的倍数).
#include#include #include #include using namespace std;typedef long long ll;const int maxn = 1e6+5;const ll mod = 998244353;int sum[maxn];ll dp[maxn];ll cal(ll x, int n){ ll s = 1; while(n > 0) { if(n & 1) s = (s*x) % mod; x = (x*x)%mod; n >>= 1; } return s;}int main(){//freopen("in", "r", stdin); int T; scanf("%d", &T); while(T--) { int n, k; scanf("%d %d", &n, &k); memset(sum, 0, sizeof(sum)); memset(dp, 0, sizeof(dp)); int MAX = 0; for(int i = 0; i < n; ++i) { int a; scanf("%d", &a); MAX = max(MAX, a); sum[a]++; } ll ans = 0; for(int i = MAX; i >= 1; --i) { int cnt = 0; for(int j = i; j <= MAX; j+=i) { cnt += sum[j]; dp[i] = (dp[i] - dp[j] + mod) % mod; } dp[i] = ((dp[i]+cal(2, cnt)-1)%mod + mod) % mod; ans = (ans + dp[i]*cal(i, k)) % mod; } printf("%lld\n", ans); } return 0;}
c2.上个莫比乌斯反演的代码，还不懂
#include#include #include #include #include #include #include #include #define LL long long#define MOD 998244353using namespace std;const int maxN = 1e6+10;int n, k, len;int pow2[maxN], num[maxN];int prime[maxN], u[maxN];bool vis[maxN];//莫比乌斯反演//F(n)和f(n)是定义在非负整数集合上的两个函数//并且满足条件F(n) = sum(f(d)) (d|n)//那么f(n) = sum(u(d)*F(n/d)) (d|n)//case 1: if d = 1, u(d) = 1//case 2: if d = p1*p2...pk, (pi均为互异素数), u(d) = (-1)^k//case 3: else, u(d) = 0;//性质1: sum(u(d)) (d|n) = 1 (n == 1) or 0 (n > 1)//性质2: sum(u(d)/d) (d|n) = phi(n)/n//另一种形式:F(d) = sum(f(n)) (d|n) => f(d) = sum(u(n/d)*F(n)) (d|n)//线性筛选求莫比乌斯反演函数代码void mobius(){ memset(vis, false,sizeof(vis)); u[1] = 1; int cnt = 0; for(int i = 2; i < maxN; i++) { if(!vis[i]) { prime[cnt++] = i; u[i] = -1; } for(int j = 0; j < cnt && i*prime[j] < maxN; j++) { vis[i*prime[j]] = true; if(i%prime[j]) u[i*prime[j]] = -u[i]; else { u[i*prime[j]] = 0; break; } } }}void init(){ mobius(); pow2[0] = 1; for (int i = 1; i < maxN; ++i) pow2[i] = 2*pow2[i-1]%MOD;}void input(){ int tmp; len = 0; scanf("%d%d", &n, &k); memset(num, 0, sizeof(num)); for (int i = 0; i < n; ++i) { scanf("%d", &tmp); len = max(len, tmp); num[tmp]++; } for (int i = 1; i <= len; ++i) { for (int j = i*2; j <= len; j += i) num[i] += num[j]; }}//快速幂m^nLL quickPow(LL x, int n){ if (n == 0) return 1; if (x == 0) return 0; LL a = 1; while (n) { a *= n&1 ? x : 1; a %= MOD; n >>= 1 ; x *= x; x %= MOD; } return a;}void work(){ int ans = 0, val; for (int i = 1; i <= len; ++i) { val = quickPow(i, k); for (int j = i; j <= len; j += i) { ans += ((LL)u[j/i]*val%MOD)*(pow2[num[j]]-1)%MOD; ans = (ans%MOD+MOD)%MOD; } } printf("%d\n", ans);}int main(){ //freopen("test.in", "r", stdin); init(); int T; scanf("%d", &T); for (int times = 1; times <= T; ++times) { input(); work(); } return 0;}