\(T1：\)交友（friend）
思路：
简单的模拟贪心。枚举每一个草出现的位置，向它的上左右下查找是否有符合条件的牛，然后进行标记，防止出现同样的两头牛相会的局面。
代码：
$code$
#include<iostream>
#include<map>
#define int long long
using namespace std;
const int N=1024,M=1e10,op=N*N;
int m,n,ans,num[N][N],cnt;char ch[N][N];map<int,bool> link;
signed main(){
// freopen("friend.in","r",stdin);
// freopen("friend.out","w",stdout);ios::sync_with_stdio(false);cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>ch[i][j];if(ch[i][j]=='C') num[i][j]=++cnt;//给牛标号 方便打标记 }}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(ch[i][j]=='G'){//遍历草 if(ch[i-1][j]=='C'&&ch[i][j-1]=='C'&&!link[num[i-1][j]*op+num[i][j-1]]){//上左有牛且并未连接 link[num[i-1][j]*op+num[i][j-1]]=link[num[i][j-1]*op+num[i-1][j]]=1;ans++;continue;}else if(ch[i-1][j]=='C'&&ch[i][j+1]=='C'&&!link[num[i-1][j]*op+num[i][j+1]]){//上右有牛且并未连接 link[num[i-1][j]*op+num[i][j-1]]=link[num[i][j-1]*op+num[i-1][j]]=1;ans++;continue;}else if(ch[i][j-1]=='C'&&ch[i][j+1]=='C'&&!link[num[i][j-1]*op+num[i][j+1]]){//左右有牛且并未连接 link[num[i][j-1]*op+num[i][j+1]]=link[num[i][j+1]*op+num[i][j-1]]=1;ans++;continue;}else if(ch[i-1][j]=='C'&&ch[i+1][j]=='C'&&!link[num[i-1][j]*op+num[i+1][j]]){//上下有牛且并未连接 link[num[i-1][j]*op+num[i+1][j]]=link[num[i+1][j]*op+num[i-1][j]]=1;ans++;continue;}else if(ch[i+1][j]=='C'&&ch[i][j-1]=='C'&&!link[num[i+1][j]*op+num[i][j-1]]){//下左有牛且并未连接 link[num[i+1][j]*op+num[i][j-1]]=link[num[i][j-1]*op+num[i+1][j]]=1;ans++;continue;}else if(ch[i+1][j]=='C'&&ch[i][j+1]=='C'&&!link[num[i+1][j]*op+num[i][j+1]]){//下右有牛且并未连接 link[num[i+1][j]*op+num[i][j+1]]=link[num[i][j+1]*op+num[i+1][j]]=1;ans++;continue;}}}}cout<<ans<<'\n';//输出答案 return 0;
}/*
4 5
.CGGC
.CGCG
CGCG.
.CC.C
*/
\(T2：\) 炼金（alchemy）
思路：
我们发现这道题很难正面找出答案，于是考虑二分答案（第10086次死在二分答案上了）。然后考虑\(check\)函数。这里我们使用负债思想，这里的配方有一点点像一棵套着环的树，于是我们就可以让“父债子偿”了。假设我们此时二分出的答案为\(ans\)，那么我们需要再用配方合成\(ans-g[1]\)的铅，这时我们需要大于\(ans-g[1]\)的合成1的\(A,B\)两种原料金属，即需要再合成\(ans-g[1]-g[A]\)的\(A\)金属。以此类推，若无法还清负债，则该答案不合法。
代码：
$code$
#include<iostream>
#include<queue>
#include<cstring>
#define int long long
using namespace std;
const int N=111;
int T,m,x,y,vis[N],now[N],g[N],head[N],cnt;queue<int> q;
struct node{int to,nxt;}e[N<<3];
inline void add(int x,int y){e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;
}//建图
inline bool check(int mid){memset(vis,0,sizeof(vis));memset(now,0,sizeof(now));while(!q.empty()) q.pop();//清空 now[1]=mid;q.push(1);//从1开始 "负债 "while(!q.empty()){int x=q.front();q.pop();vis[x]++;//访问次数+1 if(vis[x]>m) return 0;//访问次数大于金属种类数 证明有循环 结束函数 if(now[x]>2e9) return 0;//负债过多 if(now[x]<=g[x]) continue;//已经还清负债 if(head[x]) for(int i=head[x];i;i=e[i].nxt) now[e[i].to]+=now[x]-g[x],q.push(e[i].to);//父债子偿 else return 0;//没有子 偿不上负债 不合法 now[x]=g[x];//"父节点" 还清负债 }for(int i=1;i<=m;i++) if(now[i]>g[i]) return 0;//没还完 return 1;//剩下的合法
}
signed main(){
// freopen("alchemy.in","r",stdin);
// freopen("alchemy.out","w",stdout);ios::sync_with_stdio(false);cin>>T;for(int ovo=1;ovo<=T;ovo++){cin>>m;cnt=0;memset(head,0,sizeof(head));//多测清空 for(int i=1;i<=m;i++){cin>>x>>y;if(x==1||y==1||x==i||y==i) continue;//把1转化为别的金属和从自己转化为自己的情况显然不优 add(i,x);add(i,y);}for(int i=1;i<=m;i++) cin>>g[i];int l=0,r=2e9,mid;while(l<=r){//二分答案 mid=(l+r)>>1;if(check(mid)) l=mid+1;else r=mid-1;}cout<<"Case #"<<ovo<<": "<<r<<'\n';}return 0;
}
\(T3：\) 磁铁（magnet）
思路：
三维\(dp\)。设第\(i\)个磁铁分为\(j\)组，占据\(k\)的长度。对于每个新加入的点有三种转移的情况：
-
新加入的磁铁放在两组之间，相当于对两组进行合并。此时组数减一，长度增大\(2*len[i]-1\)，有\(j-1\)个空可以放，所以乘上\(j-1\)。
-
新加入的磁铁放在其中一组的一端。此时组数不变，长度增加\(len[i]\)，有\(2*(j+1)\)个空可以放（每组有两端）。
-
新加入的磁铁单开一组。此时组数加一，长度加一，有\(j+1\)个空可以放。
最后的答案为\(\sum_{i=0}^{i<=l} dp[n][1][i]*C(l-i+n,n)\)(由插板法可得，用\(n\)个元素将\(l-i\)个空分为\(n\)部分)
\(tip：\)先放辐射范围小的，这样它的辐射范围就会被接下来新放入的点的辐射范围覆盖，显然此时浪费的长度最少，情况最优，这样计算不会少情况。
代码：
$code$
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int N=10006,mod=1e9+7;
int n,l,a[N],dp[55][55][N],sum,fac[N],inv[N],ans;
inline int qpow(int x,int y){int res=1;while(y){if(y&1) res=(res*x)%mod;x=x*x%mod;y>>=1;}return res%mod;
}//快速幂
inline int C(int n,int m){return fac[n]*inv[m]%mod*inv[n-m]%mod;
}//组合数
signed main(){
// freopen("magnet.in","r",stdin);
// freopen("magnet.out","w",stdout);ios::sync_with_stdio(false);fac[0]=inv[0]=1;for(int i=1;i<N;i++){fac[i]=fac[i-1]*i%mod;inv[i]=qpow(fac[i],mod-2)%mod;}//预处理组合数 cin>>n>>l;for(int i=1;i<=n;i++) cin>>a[i];sort(a+1,a+1+n);a[n+1]=a[n];//排序 先放辐射范围小的 if(n==1){cout<<l<<'\n';return 0;}dp[0][0][0]=1;for(int i=0;i<=n;i++){for(int j=0;j<=i;j++){for(int k=0;k<=l;k++){if(j>1&&k+2*a[i+1]-1<=l) //1.合并dp[i+1][j-1][k+2*a[i+1]-1]=(dp[i+1][j-1][k+2*a[i+1]-1]+dp[i][j][k]*(j-1))%mod; if(j>0&&k+a[i+1]<=l) //2.一端 dp[i+1][j][k+a[i+1]]=(dp[i+1][j][k+a[i+1]]+dp[i][j][k]*j*2)%mod;dp[i+1][j+1][k+1]=(dp[i+1][j+1][k+1]+dp[i][j][k]*(j+1))%mod;//3.单开 }}}for(int i=0;i<=l;i++) if(dp[n][1][i]) ans=(ans+dp[n][1][i]*C(l-i+n,n)%mod)%mod;//统计答案 cout<<ans<<endl;return 0;
}