1.Tak and Cards
原题链接：http://162.14.124.219/contest/1010/problem/B
设dp[i][j][k]是在前i个数中选j（j>=1）个数、其和为k的方案总数。第i个数有选与不选2种可能，由此得出转移方程dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-a[i]](j>=1)
查看代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[1000000],dp[60][60][3600];
signed main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=0;i<=n;i++)
{
for(int j=0;j<=n;j++)
{
for(int k=0;k<=n*m;k++)
{
if(i==0&&j==0&&k==0)dp[i][j][k]=1;
else if(i>=1&&k<a[i])dp[i][j][k]=dp[i-1][j][k];
else if(i>=1&&j>=1&&k>=a[i])dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-a[i]];
else dp[i][j][k]=0;
}
}
}
int ans=0;
for(int i=1;i<=n;i++)
ans+=dp[n][i][i*m];
cout<<ans;
return 0;
}2.Coloring Edges on Tree
原题链接：http://162.14.124.219/contest/1010/problem/D
先构造邻接表，再从度数最大的点dfs图涂色
查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
const int mod=1e9+7;
vector<PII> g[1000000];
int du[1000000];
int tu[1000000];
void dfs(int x,int y)
{
int co=1;
for(int i=0;i<g[x].size();i++)
{
int a=g[x][i].first,b=g[x][i].second;
if(b==y)continue;
if(tu[y]==co)co++;
tu[b]=co++;
dfs(a,b);
}
}
signed main()
{
int n;
cin>>n;
for(int i=1;i<n;i++)
{
int x,y;
cin>>x>>y;
g[x].push_back({y,i});
g[y].push_back({x,i});
du[x]++;
du[y]++;
}
int ma=0;
for(int i=1;i<=n;i++)
{
ma=max(ma,du[i]);
}
cout<<ma<<endl;
dfs(ma,0);
for(int i=1;i<n;i++)
cout<<tu[i]<<endl;
return 0;
}