test40
教练模拟器真好玩 /kel
俄罗斯方块
旋转一下然后计数，注意对对称图形去重喵。
#pragma GCC optimize(1,2,3,"Ofast","inline")
#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)using namespace std;const int N=15;int n, m, A, B, C, D, E;
char str[N][N];signed main() {ios::sync_with_stdio(0);cin.tie(0);cin >> n >> m;up(i,1,n) cin >> (str[i]+1);up(i,1,n) up(j,1,m) if(str[i][j]!='.') {char v=str[i][j];if(v==str[i+1][j]&&v==str[i][j+1]&&v==str[i+1][j+1]) ++A;if(v==str[i][j+1]&&v==str[i][j+2]&&v==str[i][j+3]) ++B;if(v==str[i+1][j]&&v==str[i+2][j]&&v==str[i+3][j]) ++B;if(v==str[i+1][j]&&v==str[i][j+1]&&v==str[i+1][j-1]) ++C;if(v==str[i][j+1]&&v==str[i-1][j]&&v==str[i+1][j+1]) ++C;if(v==str[i][j-1]&&v==str[i+1][j]&&v==str[i+1][j+1]) ++D;if(v==str[i][j+1]&&v==str[i-1][j+1]&&v==str[i+1][j]) ++D;if(v==str[i-1][j]&&v==str[i][j-1]&&v==str[i][j+1]) ++E;if(v==str[i+1][j]&&v==str[i][j-1]&&v==str[i][j+1]) ++E;if(v==str[i-1][j]&&v==str[i+1][j]&&v==str[i][j-1]) ++E;if(v==str[i-1][j]&&v==str[i+1][j]&&v==str[i][j+1]) ++E;}cout << A << '\n' << B << '\n' << C << '\n' << D << '\n' << E << '\n';return 0;
}
矩形染色
顺着单调栈扫扫就行。
#pragma GCC optimize(1,2,3,"Ofast","inline")
#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
#define pii pair<int,int>
#define mp make_pair
#define fir first
#define sec secondusing namespace std;const int N=1000005;int n, ans;
pii u[N];signed main() {ios::sync_with_stdio(0);cin.tie(0);cin >> n;up(i,1,n) cin >> u[i].fir >> u[i].sec;up(i,1,n) u[i].fir/=2, u[i].sec/=2;sort(u+1,u+1+n,[](pii i,pii j){return i.fir>j.fir;});int lst=u[1].fir, lim=0;up(i,1,n+1) {ans+=lim*(lst-u[i].fir);lim=max(lim,u[i].sec);lst=u[i].fir;}cout << 4*ans << '\n';return 0;
}
帝国重建
设计一下 \(f_i/g_i\) 表示前缀最优答案和最后的新高度，那么希望最小化 \(f\) 再最小化 \(g\)，转移条件只有 \(h_i-h_j>g_j\) 这样，其实有决策单调性但我也没有想过为什么。但是不管怎么说，就那一个条件够做单调队列优化了，可能里面还有一个有效点的单调性。
#pragma GCC optimize(1,2,3,"Ofast","inline")
#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
#define pii pair<int,int>
#define mp make_pair
#define fir first
#define sec secondusing namespace std;const int N=1000005;int n, h[N], f[N], g[N], top=1, p[N], v[N];signed main() {ios::sync_with_stdio(0);cin.tie(0);cin >> n;up(i,1,n) cin >> h[i];up(i,2,n) h[i]+=h[i-1];up(i,1,n) {// 从后往前找第一个 h[i]>h[j]+g[j]// 所以权值在 queue 里面应该是 1 2 3 ... 向上
// dn(j,i-1,0) {
// if(h[i]-h[j]>=g[j]) {
// f[i]=f[j]+i-j-1;
// g[i]=h[i]-h[j];
// break;
// }
// }int j=p[upper_bound(v+1,v+1+top,h[i])-v-1];f[i]=f[j]+i-j-1, g[i]=h[i]-h[j];while(top&&h[i]+g[i]<=v[top]) --top;p[++top]=i, v[top]=h[i]+g[i];}cout << f[n] << '\n';return 0;
}
树上铲雪
你去想捏 dp，然后发现可以直接往上面贪心，就是那种没有后效性的题目。
#pragma GCC optimize(1,2,3,"Ofast","inline")
#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
#define pb push_backusing namespace std;const int N=200005;int n, a[N], ans;
vector<int> to[N];void dfs(int x,int fad) {int sum=0, mx=0;for(int y:to[x]) if(y!=fad) {dfs(y,x);sum+=a[y];mx=max(mx,a[y]);}if(sum<=a[x]) return;int k=(mx<=sum-mx?sum/2:sum-mx);k=min(k,min(sum-a[x],a[x])), ans+=k, a[x]-=k;if(sum-2*k>a[x]) ans+=sum-2*k-a[x];
} signed main() {ios::sync_with_stdio(0);cin.tie(0);cin >> n;up(i,1,n) cin >> a[i]; up(i,2,n) {int u, v;cin >> u >> v;to[u].pb(v);to[v].pb(u);}dfs(1,0);cout << a[1]+ans << '\n';return 0;
}