A：统计个数题，要注意ans+=a*b+c*d中，如果a*b>int，那么即使ans是long long也会越界，所以ans+=(long long)a*b+(long long)c*d
B：模拟一下删的过程
C：定义一个节点u是sad当且仅当u的子节点中存在一个节点v，使得dist(u,v)>a[v]，给定一个树，每次操作只能删除一个叶子节点，问最少删多少次后剩下来的树没有sad点。首先明确这题最后树的形态是确定的，所以这里的求最少也就相当于模拟一遍删除过程，如果我们认定一个节点是sad的（无论是否是叶子节点），那么这个节点肯定要删除不能留下（因为是从下往上删除，所以没有后效性），所以以这个节点为根的子树全部都要删除。于是算法便出来了：从根节点开始dfs，从节点u准备向其子节点遍历的时候，如果其一个子节点v使得之前遍历完的子树中的某个节点为sad，那么v就不能要，就不遍历。最终遍历到的节点就是最后删除后的子树的所有节点。具体操作就是从root开始维护一个动态最大前缀和，与a[v]比较。
#include<cstring> #include<algorithm> #include<cstdio> #include<vector> using namespace std; const int maxn=1e5; struct claris { int to; long long w; }; vector<claris> g[maxn+50]; long long a[maxn+50]; int n,s=0; void dfs(int father,int k,long long maxs) { ++s; for(int i=0;i<g[k].size();++i) { claris e=g[k][i]; if(e.to==father) continue; long long maxss=max(e.w,e.w+maxs); if(maxss>a[e.to]) continue; dfs(k,e.to,maxss); } } int main() { scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%lld",&a[i]); for(int i=2;i<=n;++i) { int p; long long c; scanf("%d %lld",&p,&c); g[i].push_back((claris){p,c}); g[p].push_back((claris){i,c}); } dfs(0,1,0); printf("%d",n-s); return 0; }
D：SB的字符串匹配DP
#include<cstring> #include<cstdio> #include<algorithm> #include<string> using namespace std; const int maxn=1e3; char a[maxn+50],b[maxn+50]; int n,m,K; int f[maxn+50][maxn+50][11],s[maxn+50][maxn+50][11]; int main() { scanf("%d %d %d ",&n,&m,&K); scanf("%s",a+1); scanf("%s",b+1); for(int k=1;k<=K;++k) for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) { s[i][j][k]=max(s[i][j-1][k],max(s[i-1][j][k],s[i-1][j-1][k])); if(a[i]!=b[j]) continue; int p=0; while(i-p>0&&j-p>0&&a[i-p]==b[j-p]) { f[i][j][k]=max(s[i-p-1][j-p-1][k-1]+p+1,f[i][j][k]); ++p; } s[i][j][k]=max(s[i][j][k],f[i][j][k]); } int ans=0; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) ans=max(ans,f[i][j][K]); printf("%d",ans); return 0; }
E：这题有点魔性……题意是给你一些整点，围成的图形面积为S，你要找一个整点三角形把所有点围起来并且三角形的面积不超过4S
官方题解：首先肯定想到先求出这些点的凸包，考虑凸包上的点围成的最大面积三角形，它的面积<S，如果把这个整点三角形的三个点作为一个大三角形每条边的中点，那么这个大三角形也是整点三角形且面积是小三角形的4倍，所以这个大三角形面积<4S，而且可以通过反证的思路证明所有点全部在这三角形内，于是问题就转化成了在凸包上找一个面积最大的三角形。采取枚举的办法，枚举两个，剩下一个是单调的，所以O（n^2）可以完成
#include<cstring> #include<algorithm> #include<cstdio> #include<cmath> using namespace std; const int maxn=5000; struct claris { long long x,y; bool operator < (const claris& p) const { return (x<p.x)||(x==p.x&&y<p.y); } }; claris a[maxn+50],p[maxn+50]; int len=0,n; long long s; bool cross(claris p,claris a,claris b) { return (double)(a.x-b.x)*(p.y-a.y)-(p.x-a.x)*(a.y-b.y)>=0; } double gets(claris p,claris a,claris b) { double s=((double)(a.x-p.x)*(b.y-p.y)-(b.x-p.x)*(a.y-p.y))/2; return abs(s); } int main() { scanf("%d %lld",&n,&s); for(int i=1;i<=n;++i) scanf("%lld %lld",&a[i].x,&a[i].y); sort(a+1,a+n+1); for(int i=1;i<=n;++i) { while(len>1&&!cross(a[i],p[len],p[len-1])) --len; p[++len]=a[i]; } int k=len; for(int i=n-1;i>=1;--i) { while(len>k&&!cross(a[i],p[len],p[len-1])) --len; p[++len]=a[i]; } if(n>1) --len; double ans=0; claris x,y,z; for(int i=1;i<=len;++i) { int last=i+2; for(int j=i+1;j<=len;++j) { int k=last; while(k<len&&gets(p[i],p[j],p[k+1])>gets(p[k],p[i],p[j])) ++k; last=k; if(gets(p[k],p[i],p[j])>ans) ans=gets(p[k],p[i],p[j]),x=p[i],y=p[j],z=p[k]; } } printf("%lld %lld ",-x.x+y.x+z.x,-x.y+y.y+z.y); printf("%lld %lld ",x.x-y.x+z.x,x.y-y.y+z.y); printf("%lld %lld",x.x+y.x-z.x,x.y+y.y-z.y); return 0; }
PS：浅谈long long的重要性……