今天写写cf上以前的水题，找找自信
A. Olesya and Rodion
此题要求一个能被t整除的n位数，直接t为开始，后面全部为0. 当然，需要排除位数为1但t=10的情况。
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 7 int main() 8 { 9 int n,t,i; 10 scanf("%d%d",&n,&t); 11 if (n==1 && t==10) 12 printf("-1 "); 13 else 14 { 15 if (t==10) 16 t=1; 17 printf("%d",t); 18 for (int i=0;i<n-1;i++) 19 printf("0"); 20 printf(" "); 21 } 22 return 0; 23 }
B. Kolya and Tanya
给你一个环，环上有3n个点，每个点的权值可以是1-3，然后问你满足a[i]+a[i+1]+a[i+2]！=6的方案有多少种，具体做法是先求出反例的情况，即a[i]+a[i+1]+a[i+2]=6的情况，这三个数的取值一共有7种，那么答案就是 3^(3n) - 7^n
1 #include<algorithm> 2 #include<iostream> 3 #include<cstdlib> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 using namespace std; 8 9 #define MOD 1000000007 10 11 int n; 12 13 LL pw(int a,int x) 14 { 15 LL k=1; 16 for (int i=1;i<=x;i++) 17 k=(k*a)%MOD; 18 return k%MOD; 19 } 20 21 int main() 22 { 23 scanf("%d",&n); 24 printf("%I64d ",(pw(27,n)-pw(7,n)+MOD)%MOD); 25 return 0; 26 }
C. Marina and Vasya
要求与两个字符串的不同字符都为t的第三个字符串。
1 #include<algorithm> 2 #include<iostream> 3 #include<cstdlib> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 using namespace std; 8 9 typedef long long LL; 10 11 #define N 100010 12 13 int n,t; 14 int ans; 15 char a[N],b[N],c[N]; 16 17 int main() 18 { 19 scanf("%d%d",&n,&t); 20 scanf("%s%s",a+1,b+1); 21 t=n-t; 22 for (int i=1;i<=n;i++) 23 if (a[i]==b[i]) 24 ans++; 25 if (ans+(n-ans)/2<t) 26 { 27 printf("-1 "); 28 return 0; 29 } 30 int k=min(t,ans); 31 for (int i=1,j=1;i<=n && j<=k;i++) 32 if (a[i]==b[i]) 33 c[i]=a[i],j++; 34 for (int i=1,j=1;i<=n && j<=t-k;i++) 35 if (a[i]!=b[i] && !c[i]) 36 c[i]=a[i],j++; 37 for (int i=1,j=1;i<=n && j<=t-k;i++) 38 if (a[i]!=b[i] && !c[i]) 39 c[i]=b[i],j++; 40 for (int i=1;i<=n;i++) 41 if (!c[i]) 42 for (int j='a';j<='z';j++) 43 if (a[i]!=j && b[i]!=j) 44 { 45 c[i]=j; 46 break; 47 } 48 printf("%s ",c+1); 49 return 0; 50 }
D. Dima and Lisa
把一个数插成1或2或3个素数
1 #include<algorithm> 2 #include<iostream> 3 #include<cstdlib> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 using namespace std; 8 9 typedef long long LL; 10 11 #define N 100010 12 13 int n; 14 15 bool check(int x) 16 { 17 for (int i=2;i<=sqrt(x);i++) 18 if (x%i==0) 19 return false; 20 return true; 21 } 22 23 int main() 24 { 25 scanf("%d",&n); 26 if (check(n)) 27 { 28 printf("1 %d",n); 29 return 0; 30 } 31 for (int i=n;i;i-=2) 32 if (check(i)) 33 { 34 int k=n-i; 35 if (check(k)) 36 { 37 printf("2 %d %d ",i,k); 38 return 0; 39 } 40 for (int j=k-2;j;j--) 41 if (check(j) && check(k-j)) 42 { 43 printf("3 %d %d %d ",i,j,k-j); 44 return 0; 45 } 46 } 47 return 0; 48 }
E. Anton and Ira
给两个数组，要求让第一个数组变成第二个数组，可以进行交换操作
每次交换操作的代价是abs(i-j)
然后让你把方案输出出来
1 #include<algorithm> 2 #include<iostream> 3 #include<cstdlib> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 using namespace std; 8 9 typedef long long LL; 10 11 #define N 2010 12 #define M 2000010 13 14 int a[N],b[N],c[N]; 15 int l[M],r[M]; 16 17 int n; 18 int ans,cnt; 19 20 int main() 21 { 22 scanf("%d",&n); 23 for (int i=1;i<=n;i++) 24 scanf("%d",&a[i]); 25 for (int i=1;i<=n;i++) 26 scanf("%d",&b[i]),c[b[i]]=i; 27 for (int i=1;i<=n;i++) 28 { 29 if (a[i]!=b[i]) 30 { 31 int k=-1; 32 for (int j=i+1;j<=n;j++) 33 if (a[j]==b[i]) 34 { 35 k=j; 36 break; 37 } 38 while (k!=i) 39 for (int j=i;j<k;j++) 40 if (c[a[j]]>=k) 41 { 42 ans+=abs(k-j); 43 swap(k,j); 44 swap(a[k],a[j]); 45 l[++cnt]=k; 46 r[cnt]=j; 47 break; 48 } 49 } 50 } 51 printf("%d %d ",ans,cnt); 52 for (int i=1;i<=cnt;i++) 53 printf("%d %d ",l[i],r[i]); 54 return 0; 55 } 56