先安利一下题目作者：一扶苏一
先看第一题：
这道题就是一道简单的模拟题，只要不管一开始的位置，模拟移动与格子对应的触发事件就行了。话不多说，看代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cctype> 4 #include<cmath> 5 6 using namespace std; 7 8 int n,m,myst,myde,hisst,hisde,hishp,lshp,ans,stax,stay; 9 int wyx[5]={0,0,0,-1,+1},wyy[5]={0,-1,1,0,0};//位移增量 10 11 char mp[105][105],ch; 12 13 inline int read() 14 { 15 ans=0; 16 ch=getchar(); 17 while(!isdigit(ch)) ch=getchar(); 18 while(isdigit(ch)) ans=(ans<<3)+(ans<<1)+ch-'0',ch=getchar(); 19 return ans; 20 } 21 22 int main() 23 { 24 freopen("mzq.in","r",stdin); 25 freopen("mzq.out","w",stdout); 26 n=read(),m=read(); 27 for(int i=1;i<=n;i++) 28 scanf("%s",mp[i]+1); 29 hishp=read(),hisst=read(),hisde=read(); 30 stax=read(),stay=read();//目前位置 31 myst=read(),myde=read(); 32 int q,a,b; 33 q=read(); 34 while(q--) 35 { 36 a=read(); 37 if(a==1)//查询操作 38 { 39 printf("%d %d %d ",lshp,myst,myde); 40 } 41 else 42 { 43 b=read(); 44 stax+=wyx[b];stay+=wyy[b];//模拟移动 45 switch(mp[stax][stay])//模拟触发事件 46 { 47 case '.':break; 48 case 'R': 49 lshp-=10; 50 if(lshp<0) lshp=0; 51 break; 52 case 'Q':myst+=5;break; 53 case 'Y':myde+=5;break; 54 case 'M':lshp+=max(1,(int)ceil(hishp/(double)max(1,myst-hisde)))*max(1,hisst-myde); 55 break; 56 } 57 } 58 } 59 return 0; 60 }
再看第二题：
爆搜显然是得不了全分的。我们从最简单的情况看起:
假如一棵树只有一个根节点u，那么答案就是uT；
如果 u 只有一个孩子 v，那么要么选 u 不选 u 的子孙，要么不选 u。不妨设以节点x为根的树的答案为fx，则不选 u 的答案即为 fv，选 u 的答案即为 uT。两种情况加起来就是 fu；
如果 u 有两个孩子 x,y。考虑要么选 u，要么只选 x 的子树内的元素，要么 只选 y 的子树内的元素，要么既选 x 内的元素又选 y 内的元素但不选 u。设 s 是 x 子树内的某个集合。考虑无论在y 的子树内怎么选，再加上 s 都是合法的，因为 y 和 x 之间没有祖先后代关系且 s 在 x 之内。设 gu 是以 u 为根能选择的集合个数，那么一共有 gy 个 集合选择 s 以后依旧合法，设 s 的权值和为 Ws，于是 s 的贡献即为 Ws×gy。由于 fx 为 x 子树内所有可能集合的权值和，所以可以发现在以x为根的子树里所有集合s的权值和为fx。于是 x 子树内的集合对答案的总贡献是 fx×gy。同理，y 子树内的集合对答案的贡献是 fy×gx。 于是 fu=fy×gx+fx×gy+fx+fy+uT。gu=gx×gy+gx+gy+1。
考虑u又有一个孩子z,那么可以把u前面的孩子看做一个子树（仔细想一下f和g的含义，这样看成整体后可以包括在前面儿子选择的所有情况，而这个整体的f即为上文中关于f的式子不加根uT的情况，g就是上文不加1的情况），那么情况就同上面第三种情况了。
见std标程：
1 #include<iostream> 2 #include<cstdio> 3 #define int long long int 4 5 namespace IPT { 6 const int L = 1000000; 7 char buf[L], *front=buf, *end=buf; 8 char GetChar() { 9 if (front == end) { 10 end = buf + fread(front = buf, 1, L, stdin); 11 if (front == end) return -1; 12 } 13 return *(front++); 14 } 15 } 16 17 template <typename T> 18 inline void qr(T &x) { 19 char ch = IPT::GetChar(), lst = ' '; 20 while ((ch > '9') || (ch < '0')) lst = ch, ch=IPT::GetChar(); 21 while ((ch >= '0') && (ch <= '9')) x = (x << 1) + (x << 3) + (ch ^ 48), ch = IPT::GetChar(); 22 if (lst == '-') x = -x; 23 } 24 25 struct Node{ 26 int nxt,to; 27 }e[1000005<<1]; 28 int head[1000005<<1]; 29 int cnt; 30 int n,T; 31 int f[1000005]; 32 int g[1000005]; 33 int w[1000005]; 34 const int Mod=1000000007; 35 inline void addedge(int u,int v){ 36 e[++cnt].nxt=head[u]; 37 e[cnt].to=v; 38 head[u]=cnt; 39 } 40 inline void dfs(int x,int fa){ 41 for(register int i=head[x];i;i=e[i].nxt){ 42 int v=e[i].to; 43 if(v==fa) continue; 44 dfs(v,x); 45 f[x]=(f[x]*g[v]+f[v]*g[x]+f[v]+f[x])%Mod; 46 g[x]=(g[x]*g[v]+g[x]+g[v])%Mod; 47 } 48 f[x]=(f[x]+w[x])%Mod; 49 g[x]=(g[x]+1)%Mod; 50 } 51 signed main(){ 52 freopen("dzy.in","r",stdin); 53 freopen("dzy.out","w",stdout); 54 qr(n); qr(T); 55 for(register int i=1;i<=n;i++) w[i]=T==1?i:1; 56 for(register int i=1;i<=n-1;i++){ 57 int x = 0,y = 0; 58 qr(x); qr(y); 59 addedge(x,y); 60 addedge(y,x); 61 } 62 dfs(1,0); 63 std::cout<<f[1]<<std::endl; 64 return 0; 65 }
再看第三题：
(Tip:捆绑测试就是一个子任务由若干个满足子任务要求的测试点组成，只有一个子任务下所有的测试点都过了，才能拿到全分，否则一分不给。）
由于题目中隐隐表达出了一种对每个点的入度的执念，便联想到了拓补排序。爆搜显然拿不到全分了，还是好好分析题目吧。先从简单的情况——DAG开始。对于一个DAG（有向无环图），一定至少有一个拓补排序。所以对一个DAG，除了一开始就入度为0的点，其他点都能通过逆序的拓补排序选上，所以只要把一开始入度不为零的点从大到小排个序，选前k个就行。
对于一个有环的图呢？可以考虑对一个强联通分量“缩点”来转化成DAG的情况，即把一个环看做一个点，那么整张图就可看成一个DAG。这时选点的情况就有两种：一是对整张图的选点，二是对单独一个环里的选点。第一种在上面已经考虑一部分了，这里考虑第二种：一个环如果没有外面的点连向他，即没有入度，那么这个环最少要剩一个点，其他点都可以通过环的搜索树的逆序选上，不妨让环中权值最小的点当那个剩下的点，这样可使局部最优。如果有入度，那么环中的点就有可能都被选。
由上，可知对能被选到的点（DAG中一开始入度不为零的点、环中能被选上的点）排个序，再找前k个就行了。进行一次 tarjan（找环算法）的复杂度是 O(n+m)，选前 k 个点可以排序一下。这样总复杂 度 O(m+nlogn)。注意到复杂度瓶颈在排序上，考虑我们只需要前 k 大而不需要具体前 k 个之间的大小关系，于是使用 std::nth_element()函数可 以将复杂度降至 O(n+m)。期望得分 40 分。注意，输入规模到了 107 级别，需要 fread 来实现读入优化。
见STD代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<string> 6 #include<queue> 7 namespace IPT { 8 const int L = 1000000; 9 char buf[L], *front=buf, *end=buf; 10 char GetChar() { 11 if (front == end) { 12 end = buf + fread(front = buf, 1, L, stdin); 13 if (front == end) return -1; 14 } 15 return *(front++); 16 } 17 } 18 19 template <typename T> 20 inline void qread(T &x) { 21 char ch = IPT::GetChar(), lst = ' '; 22 while ((ch > '9') || (ch < '0')) lst = ch, ch=IPT::GetChar(); 23 while ((ch >= '0') && (ch <= '9')) x = (x << 1) + (x << 3) + (ch ^ 48), ch = IPT::GetChar(); 24 if (lst == '-') x = -x; 25 } 26 27 28 template<typename sp> 29 inline sp mmax(sp a,sp b){ 30 return a>b?a:b; 31 } 32 template<typename sp> 33 inline sp mmin(sp a,sp b){ 34 return a>b?b:a; 35 } 36 struct Node{ 37 int nxt,from,to; 38 }e[5000005]; 39 int n,m,k,rd[1000005]; 40 int dfn[1000005],low[1000005],p[1000005]; 41 int head[1000005],cnt,top,s[1000005],sta[1000005]; 42 int tim; 43 bool vis[1000005]; 44 int minp[1000005]; 45 int ans; 46 void tarjan(int x){ 47 dfn[x]=low[x]=++tim; 48 vis[x]=true; 49 sta[++top]=x; 50 for(register int i=head[x];i;i=e[i].nxt){ 51 int v=e[i].to; 52 if(!dfn[v]){ 53 tarjan(v); 54 low[x]=mmin(low[x],low[v]); 55 } 56 else if(vis[v]) low[x]=mmin(low[x],dfn[v]); 57 } 58 if(dfn[x]==low[x]){ 59 while(true){ 60 int y=sta[top--]; 61 s[y]=x; 62 vis[y]=false; 63 if(p[y]<p[minp[x]]) minp[x]=y; 64 if(x==y) break; 65 } 66 } 67 } 68 inline void addedge(int u,int v){ 69 e[++cnt].nxt=head[u]; 70 e[cnt].from=u; 71 e[cnt].to=v; 72 head[u]=cnt; 73 } 74 int main(){ 75 freopen("zay.in","r",stdin); 76 freopen("zay.out","w",stdout); 77 qread(n);qread(m);qread(k); 78 for(register int i=1;i<=n;i++) qread(p[i]); 79 for(register int i=1;i<=n;i++) minp[i]=i; 80 for(register int i=1;i<=m;i++){ 81 int x=0,y=0; 82 qread(x);qread(y); 83 addedge(x,y); 84 } 85 for(register int i=1;i<=n;i++){ 86 if(!dfn[i]) tarjan(i); 87 } 88 for(register int i=1;i<=m;i++){ 89 int u=s[e[i].from],v=s[e[i].to]; 90 if(u==v) continue; 91 rd[v]++; 92 } 93 for(register int i=1;i<=n;i++) if(s[i]==i&&!rd[i]) p[minp[i]]=0; 94 std::sort(p+1,p+1+n); 95 //for(register int i=1;i<=n;i++) printf("%d ",p[i]); 96 for(register int i=1;i<=k;i++) ans+=p[n-i+1]; 97 std::cout<<ans<<std::endl; 98 return 0; 99 }