K Turn-by-Turn Navigation向量向量叉乘正为legt,负为right主包一开始用斜率做的浮点错误了化简成乘法其实一样#include bits/stdc.h using namespace std; #define int long long void solve(){ int n; cinn; n-2; int a1,b1,a2,b2,a3,b3; cina1b1a2b2; while(n--){ cina3b3; int x1a2-a1; int y1b2-b1; int x2a3-a1; int y2b3-b1; int k1x1*y2; int k2x2*y1; if(k1k2) coutLEFT ; else if(k1k2) coutRIGHT ; else coutSTRAIGHT ; a1a2,b1b2,a2a3,b2b3; } coutendl; } signed main() { ios::sync_with_stdio(false);cin.tie(0); int T1; cinT; while(T--){ solve(); } return 0; }几何问题一般就是向量和三角函数求不规则多边形面积将点标注连续序号按序号两两叉乘相加。L Uphill Duel这题复习一下博弈。终结点游戏结束的位置必胜态至少有一条路径可走到终结点或必败态必败态所有路径都只能走到必胜态我们是先遍历找终结点再多源BFS。#include bits/stdc.h using namespace std; typedef long long ll; typedef unsigned long long ull; struct zb { int x; int y; }; vectorint a[100005]; int fx[4][2]{{-1,0},{1,0},{0,1},{0,-1}}; int main() { ios::sync_with_stdio(false);cin.tie(0); int t; cint; while(t--) { int n,m; cinnm; for(int i0;in;i) a[i].clear(); for(int i0;in;i) { for(int j1;jm;j) { int x; cinx; a[i].push_back(x); } } queuezb dui; queuezb dui0; for(int i0;in;i) { for(int j0;jm;j) { int flag1; for(int l0;l4;l) { int x0ifx[l][0]; int y0jfx[l][1]; if(x00 || x0n || y00 || y0m) continue; if(a[x0][y0]a[i][j]) flag0; } if(flag1) { dui0.push((struct zb){i,j}); dui.push((struct zb){i,j}); } } } while(!dui0.empty()) { a[dui0.front().x][dui0.front().y]-1; dui0.pop(); } while(!dui.empty()) { int xdui.front().x; int ydui.front().y; dui.pop(); for(int l0;l4;l) { int flag0; int x0xfx[l][0]; int y0yfx[l][1]; if(x00 || x0n || y00 || y0m || a[x0][y0]0) continue; for(int l00;l04;l0) { int x1x0fx[l0][0]; int y1y0fx[l0][1]; if(x10 || x1n || y10 || y1m || (a[x1][y1]0 a[x1][y1]a[x0][y0])) continue; if(a[x1][y1]0) { flag2; break; } if(a[x1][y1]-1) flag1; } if(flag2) continue; else if(flag1) a[x0][y0]-2; else a[x0][y0]-1; dui.push((struct zb){x0,y0}); } } int q; cinq; while(q--) { int x,y; cinxy; if(a[x-1][y-1]-1) coutSecondendl; else coutFirstendl; } } return 0; }A Bitmask一个大佬队的代码妙不可言。数组的更新太简约了#include bits/stdc.h using namespace std; using ll long long; const ll INF 1ll 60; #define REP(i,n) for(ll i0; ill(n); i) template class T using V vectorT; template class A, class B void chmax(A l, const B r){ if(l r) l r; } template class A, class B void chmin(A l, const B r){ if(r l) l r; } void testcase(){ ll N; cin N; Vll A(N); REP(i,N) cin A[i]; ll cnt[30][4] {}; REP(i,N) REP(j,30) cnt[j][(A[i] j) % 4]; ll Q; cin Q; REP(qi,Q){ ll nx[30][4] {}; ll t; cin t; ll x; cin x; if(t 1){ REP(i,30) REP(j,4) nx[i][j ((x i) % 4)] cnt[i][j]; } if(t 2){ REP(i,30) REP(j,4) nx[i][j | ((x i) % 4)] cnt[i][j]; } if(t 3){ REP(i,30) REP(j,4) nx[i][j ^ ((x i) % 4)] cnt[i][j]; } REP(i,30) REP(j,4) cnt[i][j] nx[i][j]; ll ans 0; REP(i,30) ans cnt[i][1]; cout ans \n; } } int main(){ cin.tie(0)-sync_with_stdio(0); //ll T; cin T; REP(t,T) testcase(); return 0; }G Matrix Marking二维差分前缀和把标记位置放入差分数组标记数目就是当前位置(i,j)到原点矩形内所有差分数组之和。#include bits/stdc.h using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pairll, ll PII; typedef pairint, int Pii; #define IOS ios::sync_with_stdio(false),cin.tie(0), cout.tie(0); #define lowbit(x) ((x)-(x)) #define endl \n void insert(int x1, int y1, int x2, int y2, vectorvectorint b) { b[x1][y1] 1; b[x2 1][y1] - 1; b[x1][y2 1] - 1; b[x2 1][y2 1] 1; } void nzdd() { int n, m; cin n m; vectorvectorint b(n 2, vectorint(m 2, 0)); mapint, vectorPii mp; for (int i 1; i n; i) { for (int j 1; j m; j) { int t; cin t; mp[t].push_back({ i, j }); } } for (ll i 1; i mp.size(); i) { ll minc1e9, minr1e9, maxc-1e9, maxr-1e9; vectorPii x mp[i]; if (x.size() 2)continue; for (auto p : x) { ll r p.first; ll c p.second; if (c mincrminr) { insert(minr, minc, r, c, b); } if(cminc) { minr r; minc c; } if (c maxc) { if(maxr0rmaxr) insert(maxr, maxc, r, c, b); maxc c; maxr r; } } } for (int i 1; i n; i) { for (int j 1; j m; j) { b[i][j] b[i - 1][j] b[i][j - 1] - b[i - 1][j - 1]; } } for (int i 1; i n; i) { for (int j 1; j m; j) { if (b[i][j] 0) cout 1; else cout 0; } cout endl; } } int main() { IOS int _ 1; //cin _; while (_--) nzdd(); return 0; }F Not Aqre 2状压DP矩阵快速幂同类合并降复杂度J Tree.zip可并堆pbds priority queue/set,普通堆启发式合并I Swap masterB Buy One More