HGOI 20180817

首先祝各位节日快乐

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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注