A 2*2矩阵 问可不可以通过旋转 得到另外个
直接模拟
#include<stdio.h> #include<algorithm> #include<string.h> #include<string> #include<stdlib.h> #include<set> #include<iterator> #include<iostream> #include<math.h> #include<queue> #include<vector> using namespace std; #define ll long long #define inf 1000000007 #define MAXN 10000100 int x[5],z[5]; int main() { int t; scanf("%d",&t); int ca=1; while(t--) { scanf("%d%d%d%d%d%d%d%d",&z[0],&z[1],&z[3],&z[2],&x[0],&x[1],&x[3],&x[2]); int ok=0; for(int i=0;i<=3;i++) { for(int j=0;j<=3;j++) { int cnt=0; for(int k=0;k<4;k++) { if(z[(i+k)%4]==x[(j+k)%4]) cnt++; } if(cnt==4) ok=1; } } if(ok==1) printf("Case #%d: POSSIBLE ",ca++); else printf("Case #%d: IMPOSSIBLE ",ca++); } return 0; }
B给你n个数 求取其中几个 求乘积最大
排序 然后 负数 取偶数个 正数都取
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; long long a[70]; int b[3]; int main() { int t, n, i, j; scanf("%d", &t); while(t--){ scanf("%d", &n); for (i = 0; i < n; i++){ scanf("%lld", &a[i]); } sort(a, a + n); for (i = 0; i < 3; i++)b[i] = 0; for (i = 0; i < n; i++){ if (a[i] < 0)b[0]++; else if (a[i] == 0)b[1]++; else b[2]++; } long long ans = 1; for (i = 0; i < b[2]; i++){ ans *= a[n - i - 1]; } for (i = 0; i < b[0] - 1; i+=2){ ans *= (a[i] * a[i + 1]); } if (b[0] < 2 && b[2] == 0){ ans = a[0]; } if (ans < 0 && b[1] > 0)ans = 0; printf("%lld ", ans); } return 0; }
C n个数 小的可以和大的连起来 可以不相邻 连起来长度为k
问有多少个
dp[i][j] 连到第i个长度为j
dp[i][j] = sum(dp[k][j-1]); w[k]>w[i] 1 <=k<i
离散化
树状数组 维护 j-1 层 (1~i-1) 求和即可
线段树好像tle 别乱用long long
G++能过
#include<stdio.h> #include<algorithm> #include<string.h> #include<string> #include<stdlib.h> #include<set> #include<iterator> #include<iostream> #include<math.h> #include<queue> #include<vector> using namespace std; #define ll long long #define inf 1000000007 #define MAXN 1010 ll dp[MAXN][MAXN]; int z[MAXN]; int w[MAXN]; struct nod { int ind; int w; }x[MAXN]; bool cmp(nod a,nod b) { return a.w<b.w; } ll tree[MAXN]; int lowbit(ll t) { return t&(-t); } void Insert(int n,int t,ll d) { while(t<=n) { tree[t]=(tree[t]+d)%inf; t=t+lowbit(t); } } ll Ques(int t) { ll ans=0; while(t>0) { ans=(ans+tree[t])%inf; t=t-lowbit(t); } return ans; } int main() { int t; scanf("%d",&t); int ca=1; while(t--) { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&z[i]); x[i].w=z[i]; x[i].ind=i; } sort(x+1,x+n+1,cmp); w[x[1].ind]=1; int cnt=2; for(int i=2;i<=n;i++) { if(x[i].w!=x[i-1].w) w[x[i].ind]=cnt++; else w[x[i].ind]=cnt; } memset(tree,0,sizeof(tree)); for(int i=1;i<=n;i++) dp[i][1]=1; for(int k=2;k<=m;k++) { for(int i=1;i<=n;i++) { if(i>=2) Insert(cnt-1,w[i-1],dp[i-1][k-1]); ll ans=0; if(w[i]==1) ans=0; else ans=Ques(w[i]-1); dp[i][k]=ans; // printf("%d %d %lld ",i,k,ans); } memset(tree,0,sizeof(tree)); } ll ans=0; for(int i=1;i<=n;i++) ans=(ans+dp[i][m])%inf; printf("Case #%d: %lld ",ca++,ans); } return 0; } /* 3 -1 -1 -2 4 0 0 0 0 4 1 2 1 0 */
G 给你一个9*9的矩阵 问 x能不能下一个 吃掉o的
列举下的位子 然后每个o深搜 看旁边是否有 . 有点就是活的 没有就死了
#include<stdio.h> #include<algorithm> #include<string.h> #include<string> #include<stdlib.h> #include<set> #include<iterator> #include<iostream> #include<math.h> #include<queue> #include<vector> using namespace std; #define ll long long #define inf 1000000007 #define MAXN 1010 char z[12][12]; char x[12][12]; bool vis[12][12]; int s1[4]={1,0,-1,0}; int s2[4]={0,1,0,-1}; struct node { int x,y; }w[150]; int cnt; void dfs(int a,int b) { vis[a][b]=1; w[cnt].x=a; w[cnt].y=b; cnt++; for(int i=0;i<4;i++) { int c,d; c=a+s1[i]; d=b+s2[i]; if(c>=1&&c<=9&&d>=1&&d<=9&&x[c][d]=='o'&&vis[c][d]==0) dfs(c,d); } } int main() { int t; scanf("%d",&t); int ca=1; while(t--) { for(int i=1;i<=9;i++) scanf("%s",z[i]+1); int ok=0; for(int i=1;i<=9;i++) { for(int j=1;j<=9;j++) { for(int k=1;k<=9;k++) { for(int kk=1;kk<=9;kk++) x[k][kk]=z[k][kk]; } for(int k=0;k<=10;k++) x[0][k]=x[10][k]=x[k][0]=x[k][10]='x'; memset(vis,0,sizeof(vis)); if(z[i][j]=='.') { x[i][j]='x'; for(int k=1;k<=9;k++) { for(int kk=1;kk<=9;kk++) { cnt=0; if(x[k][kk]=='o'&&vis[k][kk]==0) { dfs(k,kk); int cc=0; for(int kkk=0;kkk<cnt;kkk++) { for(int kkkk=0;kkkk<4;kkkk++) { int a,b; a=w[kkk].x+s1[kkkk]; b=w[kkk].y+s2[kkkk]; if(x[a][b]=='.') cc=1; } } if(cc==0) ok=1; } } } } } } if(ok==1) printf("Case #%d: Can kill in one move!!! ",ca++); else printf("Case #%d: Can not kill in one move!!! ",ca++); } return 0; }
H队友过的
#include <stdio.h> #include <algorithm> #include <string.h> using namespace std; char s[5][5]; int biao[5]; int biao1; int di[8][2] = {{0, 1},{1, 1},{1, 0},{1, -1},{0, -1},{-1, -1},{-1, 0},{-1, 1}}; bool cmp(int i, int j){ if (s[i][j] != '*' && biao[s[i][j] - '0'] == 0)return 1; else return 0; } int main() { int t, i, j, n, k; scanf("%d", &t); int ci = 1; while(t--){ for(i = 0; i < 4; i++){ scanf("%s", s[i]); } int cnt = 0; for (i = 0; i < 4; i++){ for (j = 0; j < 4; j++) if (s[i][j] == '*')cnt++; } int q = 0; while (1){ q++; if (q >= 50)break; for (i = 0; i < 4; i++){ for (j = 0; j < 4; j++){ if (s[i][j] == '*'){ /////////////////////// for (k = 0; k <= 4; k++)biao[k] = 0; biao1 = 0; for (k = 0; k < 4; k++){ if (cmp(i, k))biao[s[i][k] - '0'] = 1, biao1++; if (cmp(k, j))biao[s[k][j] - '0'] = 1, biao1++; } for (k = 0; k < 8; k++){ int tt = i + di[k][0], ii = j + di[k][1]; if (tt >= 0 && tt <= 3 && ii >= 0 && ii <= 3){ if ((tt==1 && di[k][0] == -1) || (tt == 2 && di[k][0] == 1) || (ii == 1 && di[k][1] == -1) || (ii == 2 && di[k][1] == 1))continue; if (cmp(tt, ii))biao[s[tt][ii] - '0'] = 1, biao1++; } } if (biao1 >= 3){ for (k = 1; k <= 4; k++){ if (biao[k] == 0)s[i][j] = '0' + k, cnt--; } } //////////////// } } }/////// if (cnt <= 0)break; } printf("Case #%d: ", ci++); if (q>= 100)printf("p = %d ", q); for (i = 0; i < 4; i++){ printf("%s ",s[i]); } } return 0; }
L
2*n-1
#include <iostream> using namespace std; int main() { int T,n; cin>>T; int ans=1; while(T--) { cin>>n; cout<<"Case #"<<ans++<<": "<<2*n-1<<endl; } return 0; }