题目
A
A. Definite Game
1 2 3 4 5 6 7 8 9 #include <bits/stdc++.h> using namespace std ;int main () { int n; cin >>n; if (n==2 )cout <<2 <<endl ; else cout <<1 <<endl ; return 0 ; }
B
B. Farewell Party
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 #include <bits/stdc++.h> using namespace std ;const int N=100005 ;int a[N],b[N];int main () { int n; scanf ("%d" ,&n); for (int i=1 ;i<=n;i++){ scanf ("%d" ,&a[i]); a[i]=n-a[i]; } int f=1 ; for (int i=1 ;i<=n;i++){ if (b[i]>0 )continue ; b[i]=f; int count=a[i]-1 ; for (int j=i+1 ;j<=n;j++){ if (count==0 )break ; if (b[j]>0 )continue ; if (a[j]==a[i]){ b[j]=b[i]; count--; } } if (count>0 )f=0 ; if (f==0 )break ; f++; } if (f==0 )puts ("Impossible" ); else { puts ("Possible" ); for (int i=1 ;i<=n;i++){ printf ("%d " ,b[i]); } puts ("" ); } return 0 ; }
C
C. Colorful Bricks
he found there are k bricks with a color different from the color of the brick on its left.
n个方块,m种颜色,存在k个方块与左边相邻方块颜色不同,求涂色方案数.
排列组合问题.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 #include <bits/stdc++.h> using namespace std ;const int N=2005 ;const int MOD=998244353 ;int Comn[N][N];int Com (int n,int m) { for (int i=0 ;i<=n;i++){ Comn[i][0 ]=Comn[i][i]=1 ; for (int j=1 ;j<i;j++){ Comn[i][j]=(1l l*Comn[i-1 ][j]+Comn[i-1 ][j-1 ])%MOD; } } return Comn[n][m]; } int Qpow (int x,int y) { int ans=1 ; while (y){ if (y&1 )ans=(1l l*ans*x)%MOD; x=(1l l*x*x)%MOD; y>>=1 ; } return ans; } int main () { int n,m,k; cin >>n>>m>>k; cout <<(1l l*Com(n-1 ,k)*m%MOD*Qpow(m-1 ,k))%MOD<<endl ; return 0 ; }
D
D. Maximum Distance
E
E. Missing Numbers
依次尝试平方数。long long真是恶心。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 #include <bits/stdc++.h> #define check(x) ((long long)(sqrt(x))*(long long)(sqrt(x))==(x)) using namespace std ;const int N=100005 ;const long long M=10000000000000l l;long long a[N];int main () { int n; scanf ("%d" ,&n); for (int i=2 ;i<=n;i+=2 ){ scanf ("%lld" ,&a[i]); } long long s=0 ,k=1 ,f=1 ; for (int i=1 ;i<=n;i+=2 ){ while (1 ){ if (k*k>s&&check(k*k+a[i+1 ])){ a[i]=k*k-s; s=k*k+a[i+1 ]; k++; break ; } k++; if (k>1000000 ){ f=0 ; break ; } } if (f==0 )break ; } if (f==0 )puts ("No" ); else { puts ("Yes" ); for (int i=1 ;i<=n;i++){ printf ("%lld " ,a[i]); } puts ("" ); } return 0 ; }
F
F. Tricky Interactor
G
G. Mergesort Strikes Back
H
H. Palindromic Magic