A.直接判断每一个数。
#include<bits/stdc++.h> using namespace std; int n,a[55][55]; int main() { ios::sync_with_stdio(0); cin >> n; for(int i = 1;i <= n;i++) { for(int j = 1;j <= n;j++) cin >> a[i][j]; } for(int i = 1;i <= n;i++) { for(int j = 1;j <= n;j++) { if(a[i][j] == 1) continue; int flag = 0; for(int ii = 1;ii <= n;ii++) { for(int jj = 1;jj <= n;jj++) { if(a[ii][j]+a[i][jj] == a[i][j]) flag = 1; } } if(!flag) { cout << "No" << endl; return 0; } } } cout << "Yes" << endl; return 0; }
B.枚举直线上每一点，x，y坐标分开算，求和公式。
#include<bits/stdc++.h> using namespace std; long long m,b; int main() { ios::sync_with_stdio(0); cin >> m >> b; long long ans = 0; for(int y = 0;y <= b;y++) { long long x = (b-y)*m; ans = max(ans,(x+1)*(y+1)*y/2+(y+1)*(x+1)*x/2); } cout << ans << endl; return 0; }
C.模拟栈，每次需要整理的时候，把栈中所有出栈，因为底下的已经有序，不需要再去关注它们。
#include<bits/stdc++.h> using namespace std; int n; stack<int> s; string ss; int main() { ios::sync_with_stdio(0); cin >> n; int now = 1,ans = 0; for(int i = 1;i <= 2*n;i++) { cin >> ss; if(ss == "add") { int x; cin >> x; s.push(x); } else { if(s.empty()) { now++; continue; } if(now == s.top()) { s.pop(); now++; } else { ans++; now++; while(!s.empty()) s.pop(); } } } cout << ans << endl; return 0; }
D.直接O(k^2)的最短路，转移的时候若两个点相邻，则dis不用+1，若某一坐标之差≤2，则可以转移dis+1，若终点不lit，设一个(n+1,m+1)的点，最后结果回自动+1。
#include<bits/stdc++.h> #define INF 0x3f3f3f3f using namespace std; int n,m,k,x[10005],y[10005],vis[10005] = {0},dis[10005] = {0}; int main() { ios::sync_with_stdio(0); cin >> n >> m >> k; int s,t = 0; for(int i = 1;i <= k;i++) { cin >> x[i] >> y[i]; if(x[i] == 1 && y[i] == 1) s = i; if(x[i] == n && y[i] == m) t = i; } if(!t) { t = ++k; x[k] = n+1; y[k] = m+1; } memset(dis,0x3f,sizeof(dis)); dis[s] = 0; for(int j = 1;j <= k;j++) { int pos = -1,minn = INF; for(int i = 1;i <= k;i++) { if(!vis[i] && dis[i] < minn) { pos = i; minn = dis[i]; } } if(pos == -1) break; vis[pos] = 1; for(int i = 1;i <= k;i++) { if(vis[i]) continue; if(abs(x[pos]-x[i])+abs(y[pos]-y[i]) == 1) dis[i] = min(dis[i],dis[pos]); else if(abs(x[pos]-x[i]) <= 2 || abs(y[pos]-y[i]) <= 2) dis[i] = min(dis[i],dis[pos]+1); } } if(dis[t] == INF) cout << -1 << endl; else cout << dis[t] << endl; return 0; }
E.对于每一段，可以dp，矩阵快速幂优化，注意每一段结束和每一段开始的时候，把高于c点的值清零。
#include<bits/stdc++.h> #define MOD 1000000007 using namespace std; int n; long long k; struct xx { long long m[20][20]; }; xx mul(xx a,xx b,int len) { xx tmp; for(int i = 0;i <= len;i++) { for(int j = 0;j <= len;j++) { tmp.m[i][j] = 0; for(int k = 0;k <= len;k++) tmp.m[i][j] = (tmp.m[i][j]+a.m[i][k]*b.m[k][j])%MOD; } } return tmp; } xx qpower(xx a,long long k,int len) { xx b; memset(b.m,0,sizeof(b.m)); for(int i = 0;i <= len;i++) b.m[i][i] = 1; while(k) { if(k%2) b = mul(a,b,len); a = mul(a,a,len); k /= 2; } return b; } int main() { ios::sync_with_stdio(0); cin >> n >> k; xx base,now; for(int i = 0;i < 16;i++) { for(int j = max(0,i-1);j < min(i+2,16);j++) base.m[i][j] = 1; } now.m[0][0] = 1; for(int i = 1;i <= n;i++) { long long a,b,c; cin >> a >> b >> c; for(int j = c+1;j < 16;j++) now.m[j][0] = 0; now = mul(qpower(base,min(b,k)-a,c),now,c); for(int j = c+1;j < 16;j++) now.m[j][0] = 0; if(b >= k) break; } cout << now.m[0][0] << endl; return 0; }