Reku
0%

近期题目

Posted on Edited on In Views: Valine:

http://codeforces.com/problemset/problem/156/C 这个题目的关键在于看出修改前后的字符串ASCII码和不变，而且所有ASCII码和相同的字符串可以互相到达。 这样就做一个简单DP就可以了。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const LL mod=1000000007;
LL dp[110][3000]={};
string s;
int T;
void ff()
{
	dp[0][0]=1;
	for(int i=1;i<=100;i++)
	{
		for(int j=0;j<=(i-1)*25;j++)
		{
			for(int k=0;k<26;k++)
			{
				dp[i][j+k]+=dp[i-1][j];
				dp[i][j+k]%=mod;
			}
		}
	}
}
void work()
{
	cin>>s;
	int sum=0;
	for(int i=0;i<s.size();i++)
	{
		sum+=s[i]-'a';
	}
	LL ans=dp[s.size()][sum]-1;
	while(ans<0) ans+=mod;
	printf("%I64d\n",ans);
}
int main()
{
	ff();
	scanf("%d",&T);
	while(T--) work();
	return 0;
}

http://codeforces.com/problemset/problem/269/C 给定网络流的流量，但是没有给出方向。让你判定每个边的方向。 因为每个点的入流等于出流。所以每个点的入流等于所有相关流量的和除二。 然后我们就可以从源点开始计算，枚举相关的边，用类似拓扑排序的方法。当一个点的入流流满的时候，这个点进入队列。 要注意，汇点的入流为正无穷。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
vector<int> e[200010];
vector<bool> w[200010];
vector<int> num[200010];
vector<int> u[200010];
bool ans[200010]={};
bool v[200010]={};
int sum[200010];
int n,m;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		sum[a]+=c;
		sum[b]+=c;
		e[a].pb(b);
		w[a].pb(0);
		num[a].pb(i);
		u[a].pb(c);
		e[b].pb(a);
		w[b].pb(1);
		num[b].pb(i);
		u[b].pb(c);
	}
	for(int i=1;i<=n;i++) sum[i]/=2;
	queue<int> q;
	q.push(1);
	v[1]=1;
	while(!q.empty())
	{
		int s=q.front();
		q.pop();
		for(int i=0;i<e[s].size();i++)
		{
			if(v[e[s][i]]==0)
			{
				sum[e[s][i]]-=u[s][i];
				ans[num[s][i]]=w[s][i];
				if(sum[e[s][i]]==0&&e[s][i]!=n)
				{
					v[e[s][i]]=1;
					q.push(e[s][i]);
				}
			}
		}
	}
	for(int i=1;i<=m;i++)
	{
		cout<<ans[i];
		printf("\n");
	}
	return 0;
}

http://codeforces.com/problemset/problem/295/C 这个题是挺不错的一道题。 每个状态可以表示成\([50][50][2]\)的组（初始岸上有多少个\(50\)，多少个\(100\)，船在哪个岸）。 这样就通过bfs搜索状态就行，路径的转移用组合数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const LL mod=1000000007;
int n,k;
bool v[55][55][2]={};
int t[55][55][2]={};
LL d[55][55][2]={};
LL comb[55][55];
void init(){
    for(int i = 0; i < 55; i ++){
        comb[i][0] = comb[i][i] = 1;
        for(int j = 1; j < i; j ++){
            comb[i][j] = comb[i-1][j] + comb[i-1][j-1];
            comb[i][j] %= mod;
        }
    }
}
int a=0;
int b=0;
int c;
struct pp{
	int a,b,c;
};
int main()
{
	init();
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&c);
		if(c==50) a++;
		else b++;	
	}
	pp u;
	u.a=a; u.b=b; u.c=0;
	queue<pp> q;
	d[a][b][0]=1;
	v[a][b][0]=1;
	q.push(u);
	while(!q.empty())
	{
		u=q.front();
		pp o;
		q.pop();
		//cout<<u.a<<" "<<u.b<<" "<<u.c<<" "<<t[u.a][u.b][u.c]<<endl;
		if(u.c==0)
		{
			for(int i=0;i<=u.a;i++)
			{
				for(int j=0;j<=u.b;j++)
				{
					if(i==0&&j==0) continue;
					if(i*50+j*100<=k&&v[u.a-i][u.b-j][1]==0)
					{
						v[u.a-i][u.b-j][1]=1;
						t[u.a-i][u.b-j][1]=t[u.a][u.b][0]+1;
						LL gg=comb[u.a][i]*comb[u.b][j];
						gg%=mod;
						d[u.a-i][u.b-j][1]=d[u.a][u.b][0]*gg;
						d[u.a-i][u.b-j][1]%=mod;
						o.a=u.a-i; o.b=u.b-j; o.c=1;
						q.push(o);
					}
					else if(i*50+j*100<=k&&t[u.a-i][u.b-j][1]==t[u.a][u.b][0]+1)
					{
						LL gg=comb[u.a][i]*comb[u.b][j];
						gg%=mod;
						d[u.a-i][u.b-j][1]+=d[u.a][u.b][0]*gg;
						d[u.a-i][u.b-j][1]%=mod;
					}
				}
			}
		}
		else
		{
			for(int i=0;i<=a-u.a;i++)
			{
				for(int j=0;j<=b-u.b;j++)
				{
					if(i==0&&j==0) continue;
					if(i*50+j*100<=k&&v[u.a+i][u.b+j][0]==0)
					{
						v[u.a+i][u.b+j][0]=1;
						t[u.a+i][u.b+j][0]=t[u.a][u.b][1]+1;
						LL gg=comb[a-u.a][i]*comb[b-u.b][j];
						gg%=mod;
						d[u.a+i][u.b+j][0]=d[u.a][u.b][1]*gg;
						d[u.a+i][u.b+j][0]%=mod;
						o.a=u.a+i; o.b=u.b+j; o.c=0;
						q.push(o);
					}
					else if(i*50+j*100<=k&&t[u.a+i][u.b+j][0]==t[u.a][u.b][1]+1)
					{
						LL gg=comb[a-u.a][i]*comb[b-u.b][j];
						gg%=mod;
						d[u.a+i][u.b+j][0]+=d[u.a][u.b][1]*gg;
						d[u.a+i][u.b+j][0]%=mod;
					}
				}
			}
		}
	}
	if(v[0][0][1]==0)
	{
		cout<<-1<<endl;
		cout<<0;
		return 0;
	}
	cout<<t[0][0][1]<<endl;
	cout<<d[0][0][1];
	return 0;
}

http://codeforces.com/problemset/problem/286/C 解决括号问题一般来说都用栈来解决。 但是这道题并不能用栈来正着贪心，因为并不能确定是否更改。 但是倒着贪心是可以的，如果能消去括号就消去，如果不能，那就更改为一个新的括号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
using namespace std;
int n,t;
int p[1000100]={};
int num[1000100]={};
bool cmp(int x,int y)
{
	return x<y;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&p[i]);
 	}
	scanf("%d",&t);
	for(int i=1;i<=t;i++)
	{
		int o;
		scanf("%d",&o);
		p[o]=-p[o];
	}
	int w=0;
	for(int i=n;i>=1;i--)
	{
		if(p[i]<0) num[++w]=-p[i];
		else if(num[w]==p[i]) w--;
		else
		{
			num[++w]=p[i];
			p[i]=-p[i];
		}
	}
	if(w) printf("NO");
	else
	{
		printf("YES\n");
		for(int i=1;i<=n;i++) printf("%d ",p[i]);
	}
	return 0;
}

http://codeforces.com/problemset/problem/449/C 构造题。 首先找到所有的大于2的质数，然后找数列中未匹配的、能整除质数\(d\)的数字。如果数字的个数是偶数，就直接进行匹配。如果是奇数，就把\(2 \times d\)拿出去（如果存在的话）。 这样的话，能保证所有存在匹配的数字，如果数字个数是奇数，那就只有一个匹配不到。如果数字个数是偶数，那所有数字都能匹配到。一定是最优的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e5;

bool iscomp[maxn+5], vis[maxn+5];

void prime_table(int n) {
    for (int i = 2; i * i <= n; i++) {
        if (iscomp[i])
            continue;
        for (int j = i * i; j <= n; j += i)
            iscomp[j] = 1;
    }
}

int main () {
    int n;
    scanf("%d", &n);
    prime_table(n);

    vector<int> g;
    vector<pii> ans;

    for (int i = n / 2; i > 1; i--) {
        if (iscomp[i])
            continue;
        g.clear();

        for (int j = i; j <= n; j += i) {
            if (vis[j] == 0)
                g.push_back(j);
        }
        if (g.size() & 1)
            swap(g[1], g[g.size()-1]);
        for (int i = 0; i < g.size() - 1; i += 2) {
            ans.push_back(make_pair(g[i], g[i+1]));
            vis[g[i]] = vis[g[i+1]] = 1;
        }
    }

    printf("%lu\n", ans.size());
    for (int i = 0; i < ans.size(); i++)
        printf("%d %d\n", ans[i].first, ans[i].second);
    return 0;
}