3 算法题小总结( 二 ) _整数

For each test case :
“YES”, if thebe ;
“NO”, .
You may print everyin any case you want (so, for , theyEs, yes, Yes and YES are allas).
input
ABA
11
AB
NO
NO
YES
YES
YES*/
思路
判断字符串是否重复出现，不必多说
代码展示
#include #include int main(){char a[1001];int b[1001] = {0};int n, i, j, k, len;scanf("%d", &n);for (i = 0; i < n; i++) {scanf("%d", &len);scanf("%s", a);for (j = 0; j < len; j++) {if (a[j] != a[j - 1]) {for (k = 0; k < j; k++) {if (a[k] == a[j]) {b[i] = 1;break;}}}if (b[i] == 1)break;}}for (i = 0; i < n; i++) {if (b[i] == 0)printf("YES\n");elseprintf("NO\n");}return 0;}
3.过河卒
思路
把马和马能到的地方标记，然后按顺序对坐标进行更新，a[x,y]=a[x-1,y]+a[x,y-1],最后输出a[x,y]的值。
代码展示
#includeint main(){int x1,x2,y1,y2;long long int a[30][30];scanf("%d%d%d%d",&x1,&y1,&x2,&y2);//所有不能通过的位置 a[x2][y2]=-1;if(y2-2>=0 && x2+1<=x1)a[x2+1][y2-2]=-1;if(y2-2>=0 && x2-1>=0)a[x2-1][y2-2]=-1;if(y2-1>=0 && x2+2<=x1)a[x2+2][y2-1]=-1;if(y2-1>=0 && x2-2>=0)a[x2-2][y2-1]=-1;if(y2+1<=y1 && x2+2<=x1)a[x2+2][y2+1]=-1;if(y2+1<=y1 && x2-2>=0)a[x2-2][y2+1]=-1;if(y2+2<=y1 && x2+1<=x1)a[x2+1][y2+2]=-1;if(y2+2<=y1 && x2-1>=0)a[x2-1][y2+2]=-1;for(int i=1;i<=x1;i++){if(a[0][i]==-1){for(int j=i+1;j<=y1;j++){if(a[0][j]!=-1)a[0][j]=0;}break;}else{a[0][i]=1;}}for(int i=1;i<=y1;i++){if(a[i][0]==-1){for(int j=i+1;j<=x1;j++){if(a[j][0]!=-1)a[j][0]=0;}break;}else{a[i][0]=1;}}for(int i=1;i<=x1;i++)for(int j=1;j<=y1;j++){if(a[i][j]!=-1){if(a[i-1][j]==-1&&a[i][j-1]==-1){a[i][j]=0;}else if(a[i-1][j]==-1&&a[i][j-1]!=-1){a[i][j]=a[i][j-1];}else if(a[i-1][j]!=-1&&a[i][j-1]==-1){a[i][j]=a[i-1][j];}else if(a[i-1][j]!=-1&&a[i][j-1]!=-1){a[i][j]=a[i][j-1]+a[i-1][j];}}}printf("%lld\n",a[x1][y1]);return 0;}
#includelong long dp[30][30];int main(){int n,m,a,b,i,j;scanf("%d%d%d%d",&a,&b,&n,&m);m++;n++;a++;b++;for(i=1;i<=a;i++)for(j=1;j<=b;j++){if(i==1 && j==1)dp[i][j] = 1;else if((i==n&&j==m) || (i==n-1&&j==m-2) || (i==n-2&&j==m-1) || (i==n-2&&j==m+1) || (i==n-1&&j==m+2) || (i==n+1&&j==m+2)|| (i==n+2&&j==m+1) || (i==n+2&&j==m-1) || (i==n+1&&j==m-2))dp[i][j]=0;else if(i!=1 || j!=1)dp[i][j] = dp[i-1][j]+dp[i][j-1];}printf("%lld\n",dp[a][b]);return 0;}
4.地毯
思路
1.三个循环暴力破解，在覆盖的地方+1
2.先二维差分再二维前缀和
代码展示
三个循环暴力破解（不出意外会超时）
#include int a[1001][1001] = {0};int main() {int x1, y1, x2, y2;int n, m;scanf("%d %d", &n, &m);for (int i=1;i<=m;i++) {scanf("%d%d%d%d",&x1,&y1,&x2,&y2);for(int j=x1;j<=x2;j++)for(int k=y1;k<=y2;k++){a[j][k]++;}}for (int i=1;i<=n;i++) {for (int j=1;j<=n;j++) {printf("%d ",a[i][j]);}printf("\n");}return 0; }
前缀和
#includeint a[1005][1005]={0};int main(){int n,m,x1,x2,y1,y2;scanf("%d %d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d%d%d",&x1,&y1,&x2,&y2);for(int j=x1;j<=x2;j++){a[j][y1]+=1;a[j][y2+1]-=1;}}for(int i=1;i<=n;i++)//每一行 {for(int j=1;j<=n;j++)//每一列{a[i][j]+=a[i][j-1];//前缀和 }}//输出操作 for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){-printf("%d ",a[i][j]);}printf("\n");}return 0;}
5.最小新整数
/*给定一个十进制正整数n(0 现在从 m 位中删除 k 位 (0 例如:n=,k=2, 则生成的新整数最小为 12456 。
输入格式
第一行 t, 表示有 t 组数据；
接下来 t 行，每一行表示一组测试数据，每组测试数据包含两个数字 n,k 。
输出格式
t 行，每行一个数字，表示从 n中删除 k位后得到的最小整数。
Input