C：
题意：
有n个整数ai，数列a有两个神奇的性质。1.所有的整数都在[l,r]范围内。2.这n个数的和能被3整除。现在给出l和r，和个数n，问你有多少种方法构造出数列a，方案数mod1e9+7.
题解：
一个数被3除只有三种可能。1.整除，2.余1，2.余2.
然后我们再想这个问题，[l,r]区间内，能被3整除的数有多少？a0=r/3-l/3。余1/2的数有多少？a1/2=((r-l+1)-a0)/2.（这里具体余1和余2不重要，想想为什么）
我们设f[i][j]为前i个数，和除3余j的方案数。怎么转移呢。
f[i][0]=f[i-1][1]*a2+f[i-1][2]*a1+f[i-1][0]*a0.
f[i][1]=f[i-1][0]*a1+f[i-1][1]*a0+f[i-1][2]*a2.
f[i][2]=f[i-1][0]*a2+f[i-1][1]*a1+f[i-1][2]*a0.
#include<stdio.h>
#include<iostream>
using namespace std; long long dp[][];
const long long mod=;
int main(){
int n,l,r;
cin>>n>>l>>r;
long long a0,a1,a2;
long long sum=r-l+;
a0=r/-(l-)/;
sum-=a0;
a1=sum/;
a2=sum-a1 ;
dp[][]=a0;
dp[][]=a1;
dp[][]=a2;
for(int i=;i<=n;i++)
{
dp[i][]=(dp[i-][]*a2+dp[i-][]*a0+dp[i-][]*a1)%mod;
dp[i][]=(dp[i-][]*a0+dp[i-][]*a1+dp[i-][]*a2)%mod;
dp[i][]=(dp[i-][]*a1+dp[i-][]*a2+dp[i-][]*a0)%mod;
}
printf("%I64d\n",dp[n][]); }
D.题意
kilani正在和朋友们玩一个游戏，这个游戏在一个n*m的网格上，每个格子要么是空白，要么是已经被占领，每个玩家有一个或者多个城堡。每个玩家轮流进行游戏。对于玩家i，他可以从一个已有的城堡向一个空白的格子扩建一个城堡，如果这个空白的格子和它的曼哈顿距离不超过s[i]。
求游戏结束后每个玩家占领的格子数量。
题解：
一个多源bfs。具体可以看代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue> #define pir pair<int,int>
#define mkp make_pair
using namespace std;
const int maxn=+;
const int dx[]={,,,-};
const int dy[]={,-,,}; int n,m,p;
int a[],ans[];
char G[maxn][maxn];
int vis[maxn][maxn];
struct Node{
int x,y,p;
};
int main(){
scanf("%d%d%d",&n,&m,&p);
for(int i=;i<=p;i++){
scanf("%d",&a[i]);
}
queue<pir>q;
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
scanf(" %c",&G[i][j]);
}
}
for(int k=;k<=p;k++){
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
// scanf(" %c",&G[i][j]);
if(G[i][j]!='.'&&G[i][j]!='#'&&G[i][j]-''==k){
vis[i][j]=k;
q.push(mkp(i,j));
}
}
}
} while(!q.empty()){
pir u=q.front();q.pop();
int x=u.first,y=u.second;
int num=vis[x][y];
queue<Node>q2;
q2.push({x,y,a[num]});
while(!q.empty()){
pir u1=q.front();
if(vis[u1.first][u1.second]==num){
q.pop();
q2.push({u1.first,u1.second,a[num]});
}else{
break;
}
} while(!q2.empty()){
Node u1=q2.front();q2.pop();
if(u1.p<=)continue;
for(int k=;k<;k++){
int nx=u1.x+dx[k];
int ny=u1.y+dy[k];
if(nx>=&&nx<=n&&ny>=&&ny<=m&&G[nx][ny]=='.'&&vis[nx][ny]==){
vis[nx][ny]=num;
q2.push({nx,ny,u1.p-});
q.push(mkp(nx,ny));
}
}
} } for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(vis[i][j]){
ans[vis[i][j]]++;
//printf("%d ",vis[i][j]);
}
}
//printf("\n");
} for(int i=;i<=p;i++){
printf("%d ",ans[i]);
}
return ;
}
E. Helping Hiasat
题意：
Hiasat有一个社交账号，当他的朋友们每次来看他社交首页的时候，如果他首页的名字是这个朋友的名字，他朋友就会很开心。给出一个序列代表可以修改名字的时间和朋友们来访问的顺序，问如何修改才能让开心的朋友们最多。
题解：
显然在两次修改之间的所有访问，只能满足一次。那么其实很显然，将这些点之间连边，然后求图的最大独立集。然后最大独立集怎么求？求补图中的最大团。最大团怎么求？套板子啊！！
include <bits/stdc++.h>
using namespace std;
const int maxn = ;
bool mp[maxn][maxn];
int num[maxn], group[maxn], now[maxn];
int n, m, ans;
bool dfs(int u, int cnt)
{
int i, j;
for(i = u+; i <= n; ++i)
{
if(num[i]+cnt <= ans) return false; //��֦3
if(mp[u][i])
{
for(j = ; j < cnt; ++j)
if(!mp[i][now[j]]) break;
if(j == cnt) //�Ż�
{
now[cnt] = i;
if(dfs(i, cnt+)) return true;
}
}
}
if(cnt > ans)
{
for(i = ; i < cnt; ++i)
group[i] = now[i];
ans = cnt;
return true;
}
return false;
} int MaximumClique()
{
ans = -;
for(int i = n; i >= ; --i)
{
now[] = i;
dfs(i, );
num[i] = ans;
}
return ans;
}
map<string,int>Name;
int name_num;
int N,M;
int G[maxn][maxn]; int main()
{
scanf("%d%d",&N,&M);
vector<int>per;
set<int>S;
for(int i=;i<=N;i++){
int type;
scanf("%d",&type);
if(type==){
per.clear();
S.clear();
}else{
string name;
cin>>name;
if(!Name.count(name)){
Name[name]=++name_num;
}
if(!S.count(Name[name])){
S.insert(Name[name]);
for(int i=;i<per.size();i++){
int u=per[i];
G[u][Name[name]]=;
G[Name[name]][u]=;
}
per.push_back(Name[name]);
}
}
}
n=name_num;
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
mp[i][j]=!G[i][j];
}
}
printf("%d\n",MaximumClique());
// while(cin >> n && n)
// {
// for(int i = 1; i <= n; ++i)
// for(int j = 1; j <= n; ++j)
// {
// int x; cin >> x;
// mp[i][j] = x;
// }
// cout << MaximumClique() << endl;
// }
return ;
}