首页 > 代码库 > Codeforces Round #420 (Div. 2)
Codeforces Round #420 (Div. 2)
/******************************************************************************************************************
因为发现不敲题会变蠢...所以没事还是做两道题吧....
很久没做过题然后发现C和E全都是因为没用LL给卡住了...... 我真的是太蠢了
*******************************************************************************************************************/
A. Okabe and Future Gadget Laboratory
暴力判断就行了
1 #include<stdio.h> 2 #include<string.h> 3 #include<iostream> 4 using namespace std; 5 int Map[55][55]; 6 int main() 7 { 8 int n; 9 scanf("%d",&n);10 for(int i=1;i<=n;++i)11 for(int j=1;j<=n;++j)12 scanf("%d",&Map[i][j]);13 int Ans=1;14 for(int i=1;i<=n;++i)15 for(int j=1;j<=n;++j)16 if(Map[i][j]!=1)17 {18 int flag=0;19 for(int k=1;k<=n;++k)20 if(k!=i&&!flag)21 for(int q=1;q<=n;++q)22 if(q!=j&&Map[i][q]+Map[k][j]==Map[i][j]&&!flag)23 flag=1;24 if(!flag)25 Ans=0;26 }27 printf("%s\n",Ans?"Yes":"No");28 return 0;29 }
B. Okabe and Banana Trees
发现高度会很小,所以直接遍历高度,然后就是一个等差数列求前缀和了
1 #include<stdio.h> 2 #include<string.h> 3 #include<iostream> 4 using namespace std; 5 #define LL long long 6 LL Sum[10000005]; 7 int main() 8 { 9 int m,b;10 scanf("%d%d",&m,&b);11 for(int i=1;i<=m*b;++i)12 Sum[i]=Sum[i-1]+i;13 LL Ans=0;14 for(LL i=0;i<=b;++i)15 {16 LL x=m*(b-i);17 LL tmp=0;18 tmp+=(i+1)*Sum[x];19 tmp+=(i*(i+1))*(x+1)/2;20 Ans=max(Ans,tmp);21 }22 printf("%lld\n",Ans);23 return 0;24 }
C. Okabe and Boxes
这道题比较巧妙
暴力解法：(当然是不行滴
1.如果刚好能拿走就拿走
2.不能拿走我就排序
题目说肯定存在一个答案能满足条件,就说明在第i次remove的时候i一定在序列里
所以我们在remove的时候栈顶只有两种情况
1.刚好是我们需要的
2.是我们不需要的值(这时候就直接排序
然后我们考虑之前说过的条件,remove时候i一定在序列里,然后我们考虑把所有排过序的数字给标记一下(并不排序,只是标记一下
就有了第三种情况
3.遇到了我们标记过的值
这时候因为i一定在序列里,然后考虑比i小的全都remove走了,所以如果遇到了标记的说明这时候直接把i拿走就好了,因为这时候栈里面肯定全都是排好序的
然后我们就发现了栈的相对顺序是不变的,所以每次排序我们只需要标记栈顶的那个元素
然后说是要取i,其实就是假装i取取走了,其实还是在栈里
总的来说就是当delete的时候
1.如果刚好能拿走就拿走
2.不能拿走我就标记一下栈顶(假装排序
1 #include<stdio.h> 2 #include<string.h> 3 #include<iostream> 4 using namespace std; 5 #define LL long long 6 #define maxn 500005 7 int stac[maxn]; 8 char str[15]; 9 int main()10 {11 int n;12 int st=0,ed=0;13 scanf("%d",&n);14 int pos=0,Ans=0;15 for(int i=1;i<=n*2;++i)16 {17 scanf("%s",str);18 if(str[0]==‘a‘)19 {20 int x;21 scanf("%d",&x);22 stac[ed++]=x;23 }24 else25 {26 pos++;27 if(stac[ed-1]==pos)28 {29 ed--;30 continue;31 }32 else if(stac[ed-1]==0)33 {34 continue;35 }36 else37 {38 Ans++;39 stac[ed-1]=0;40 }41 }42 }43 printf("%d\n",Ans);44 return 0;45 }
D. Okabe and City
待补
E. Okabe and El Psy Kongroo
这道题第一眼递推,然后发现k有点大.然后发现n特别小,所以就很明显的按阶段来跑矩阵快速幂
f[i+1][j]=f[i][j-1] + f[i][j] + f[i][j+1]然后判断一下会不会溢出就好了,中间用个数组存放中间值,主要是害怕用到本来应该溢出的值
1 #include<stdio.h> 2 #include<string.h> 3 #include<iostream> 4 #include<algorithm> 5 #include<math.h> 6 #include<queue> 7 #include<stack> 8 #include<string> 9 #include<vector> 10 #include<map> 11 #include<set> 12 using namespace std; 13 #define lowbit(x) (x&(-x)) 14 typedef long long LL; 15 const int maxn = 100005; 16 const int inf=(1<<28)-1; 17 #define Matrix_Size 20 18 LL MOD=1000000007; 19 int Size; 20 struct Matrix 21 { 22 LL mat[Matrix_Size][Matrix_Size]; 23 void clear() 24 { 25 memset(mat,0,sizeof(mat)); 26 } 27 void output() 28 { 29 for(int i = 0;i < Size;i++) 30 { 31 for(int j = 0;j < Size;j++) 32 printf("%d ",mat[i][j]); 33 printf("\n"); 34 } 35 } 36 Matrix operator *(const Matrix &b)const 37 { 38 Matrix ret; 39 for(int i = 0;i < Size;i++) 40 for(int j = 0;j < Size;j++) 41 { 42 ret.mat[i][j] = 0; 43 for(int k = 0;k < Size;k++) 44 { 45 long long tmp = (long long)mat[i][k]*b.mat[k][j]%MOD; 46 ret.mat[i][j] = (ret.mat[i][j]+tmp); 47 if(ret.mat[i][j]>=MOD) 48 ret.mat[i][j] -= MOD; 49 50 } 51 } 52 return ret; 53 } 54 }; 55 Matrix pow_M(Matrix a,long long n) 56 { 57 Matrix ret; 58 ret.clear(); 59 for(int i = 0;i < Size;i++) 60 ret.mat[i][i] = 1; 61 Matrix tmp = a; 62 while(n) 63 { 64 if(n&1)ret = ret*tmp; 65 tmp = tmp*tmp; 66 n>>=1; 67 } 68 return ret; 69 } 70 int S[17]; 71 int main() 72 { 73 Matrix A,B; 74 S[0]=1; 75 LL n,k; 76 scanf("%lld%lld",&n,&k); 77 for(int i=1;i<=n;++i) 78 { 79 LL st,ed,h; 80 scanf("%lld%lld%lld",&st,&ed,&h); 81 if(i==n) 82 ed=k; 83 84 Size=h+1; 85 86 B.clear(); 87 for(int j=0;j<=h;++j) 88 { 89 B.mat[0][j]=S[j]; 90 } 91 92 A.clear(); 93 for(int j=0;j<=h;++j) 94 { 95 if(j>0) 96 A.mat[j-1][j]=1; 97 A.mat[j][j]=1; 98 if(j<h) 99 A.mat[j+1][j]=1;100 }101 102 A=pow_M(A,ed-st);103 B=B*A;104 105 for(int j=0;j<17;++j)106 S[j]=0;107 108 for(int j=0;j<=h;++j)109 S[j]=B.mat[0][j];110 111 }112 printf("%d\n",B.mat[0][0]);113 return 0;114 }
Codeforces Round #420 (Div. 2)