首先祝各位节日快乐
T1 CF359A
斯波题，若四条边界上有1，直接输出2，否则输出4。好玩的是我还成功误导了某位同学，使他误以为是DFS（笑）。
#include<bits/stdc++.h>
#define N 101
using namespace std;
int n,m;
int main(){
freopen("table.in","r",stdin);
freopen("table.out","w",stdout);
cin>>n>>m;
int flag=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int x;
cin>>x;
if (x)
if (i==1||i==n||j==1||j==m) flag=1;
}
}
if (flag) cout<<2; else cout<<4;
return 0;
}
T2 CF17C
考场上愣是没看出来DP，惨遭20。其实正解也不难，见下。
将连续的相同字符压缩为同一个，
例如aabbaacc即为abac
我们可以发现，字母的顺序是不会换的，比如abac就不可能变换为abca。
所以就可以用类似背包的思想，f[i][x][y][z]代表最后一个选的字符是原串第i位，用了x个a y个b z个c的答案。
方程就是
f[nex[i][0]][a+1][b][c]=(f[nex[i][0]][a+1][b][c]+f[i][a][b][c]);
f[nex[i][1]][a][b+1][c]=(f[nex[i][1]][a][b+1][c]+f[i][a][b][c]);
f[nex[i][2]][a][b][c+1]=(f[nex[i][2]][a][b][c+1]+f[i][a][b][c]);
其中next[i][0..2]为预处理原串字符i后面（包括自身）最近的’a”b”c’的位置。
代码如下
#include<bits/stdc++.h>
#define ll long long
#define mod 51123987
using namespace std;
int n,nex[210][3],stand;
ll f[155][55][55][55],ans;
char c[155];
bool check(int a,int b,int c){
return (a+b+c==n)&&(fabs(a-b)<=1)&&(fabs(c-b)<=1)&&(fabs(a-c)<=1);
}
int main(){
freopen("balance.in", "r", stdin);
freopen("balance.out", "w", stdout);
cin>>n;
cin>>c;
nex[n+1][0]=nex[n+1][1]=nex[n+1][2]=n+1;
for(int i=n;i>=1;i--){
nex[i][0]=nex[i+1][0],nex[i][1]=nex[i+1][1],nex[i][2]=nex[i+1][2];
nex[i][c[i-1]-'a']=i;
}
ans=0,stand=(n+2)/3,f[1][0][0][0]=1;
for(int i=1;i<=n;i++)
for(int a=0;a<=stand;a++)
for(int b=0;b<=stand;b++)
for(int c=0;c<=stand;c++){
if(check(a,b,c)){
ans+=f[i][a][b][c];
}
if(nex[i][0]<=n) f[nex[i][0]][a+1][b][c]=(f[nex[i][0]][a+1][b][c]+f[i][a][b][c])%mod;
if(nex[i][1]<=n) f[nex[i][1]][a][b+1][c]=(f[nex[i][1]][a][b+1][c]+f[i][a][b][c])%mod;
if(nex[i][2]<=n) f[nex[i][2]][a][b][c+1]=(f[nex[i][2]][a][b][c+1]+f[i][a][b][c])%mod;
}
cout<<ans%mod<<endl;
return 0;
}
T3 CF19E
如果熟悉二分图和各种树上操作的话应该不难（但是我不会）。
思路很明确：给一张无向图，求删掉哪几条边可以变成二分图；
定义一个环为奇环当且仅当环包含的边数为奇数，偶环同理。
我们会发现，
如果没有奇环，那么任何边都可以删；
如果只有一个奇环，那么奇环上的边都可以被删；
如果多于1个，必须选在所有奇环且不在偶环上的点；
那么怎么找奇环呢？
这里要说到DFS树的两个特点，第一，树上的边要么构成一条链，要么是返祖边。第二，树上的LCA就是深度较浅的点。
这里的返祖边就是我们要找的环了。考虑到树上差分，它应该在两个端点+1，LCA-2。根据上面的第二点，我们将深度较浅的点+1-2即可。
统计tag==n的点，输出他的father即可。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define ri register int
#define il inline
#define fi first
#define se second
#define mp make_pair
#define pi pair<int,int>
#define mem0(x) memset((x),0,sizeof (x))
#define mem1(x) memset((x),0x3f,sizeof (x))
#define gc getchar
#define pb push_back
template<class T>void in(T &x){
x = 0; bool f = 0; char c = gc();
while (c < '0' || c > '9') {if (c == '-') f = 1; c = gc();}
while ('0' <= c && c <= '9') {x = (x << 3) + (x << 1) + (c ^ 48); c = gc();}
if (f) x = -x;
}
#undef gc
void out(int x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) out(x / 10);
putchar(x % 10 + '0');
}
#define N 10010
#define M N<<2
int n, m;
int v[M], u[M], nx[M], k[M];
int cnt = 1, head[N];
il void add(int uu, int vv) {
u[++cnt] = uu, v[cnt] = vv, nx[cnt] = head[uu];
head[uu] = cnt;
k[cnt] = (cnt >> 1);
}
int dep[N];
bool vis[N];
int tag[N];
int zt;
vector<int>ans;
int lst;
void dfs(int x, int f, int d) {
//printf("V %d\n",x);
dep[x] = d;
vis[x] = 1;
for (ri i = head[x]; i; i = nx[i]) {
if (i == f) continue;
if (!vis[v[i]]) {
dfs(v[i], i ^ 1, d + 1);
}
else {
if (dep[v[i]] < dep[x]) continue;
if ((dep[v[i]] - dep[x] + 1) & 1) {
tag[x]--; // in fact +1 -2
tag[v[i]]++;
zt++;
lst=k[i];
}
else {
tag[x]++;
tag[v[i]]--;
}
}
}
}
int dfs2(int x, int f) {
vis[x] = 1;
int res = tag[x];
for (ri i = head[x]; i; i = nx[i]) {
if (vis[v[i]]) continue;
res += dfs2(v[i], i);
}
if (res == zt) ans.pb(k[f]);
//printf("T %d %d %d\n",x,res,tag[x]);
return res;
}
signed main() {
in(n), in(m);
for (ri i = 1, a, b; i <= m; ++i) {
in(a), in(b);
add(a, b);
add(b, a);
}
for (ri i = 1; i <= n; ++i) {
if (!vis[i]) dfs(i, 0, 0);
}
if (zt == 0) {
//cout << "A";
printf("%d\n", m);
for (ri i = 1; i <= m; ++i) printf("%d ", i);
return 0;
}
if(zt==1) ans.pb(lst);
//cout<<zt;
mem0(vis);
for (ri i = 1; i <= n; ++i) {
if (!vis[i]) dfs2(i, 0);
}
sort(ans.begin(), ans.end());
printf("%d\n", ans.size());
for (ri i = 0; i < ans.size(); ++i) {
printf("%d ", ans[i]);
}
return 0;
}