Shen Huang's Blog
0%

Posted on Edited on

先给出结论，然后给出几道例题

结论

如果一个动态规划方程能够用矩阵乘法来进行优化，那么必须满足：
  1. 状态必须是一维或者两维。超过两维的情况，可以通过把多维状态压缩到一维的方法降到两维（其实就是一个pre一个now表示i+1和i并没有降低状态数）
  2. 每个状态dp[i][j]必须满足只和dp[i-1][k]有关，并且这是一个线性关系。
  3. 转移矩阵需要都相同或者至少是循环出现的，才能使用快速幂来加速矩阵乘法。
  4. 假设第一维的大小是N，第二维的大小是M，那么矩阵乘法的时间复杂度为O(M^3logN)，而直接转移的复杂度至多是O(M^2N)，有时候甚至更小，通常只有M很小的时候并且N相当大的时候才会使用矩阵乘法，否则不值得。

POJ 3744 Scout YYF I

题意：

你在一条布满地雷的道路上，开始在坐标1。每次有概率P向前走一步，有概率1-P向前走两步。道中路某几个点上会有地雷，问你安全通过的概率。地雷数N<=10，坐标范围在100000000内。

dp的方程还是很好想的dp[i] = p * dp[i-1] + (1-p) * dp[i-2]，但是n比较大直接转移不行，考虑通过矩阵快速幂解决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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const ll mod = 1000000007ll;
int num[12];double p;
#define N 10
double Mat[N][N];
void product_mod(double a[][N], double b[][N], int n) {
    double c[N][N] = {};
    for ( int i=0; i<n; i++) {
        for ( int j=0; j<n; j++) {
            for ( int k=0; k<n; k++) {
                c[i][j] += a[i][k] * b[k][j];
            }
        }
    }
    for ( int i=0; i<n; i++) {
        for ( int j=0; j<n; j++) {
            a[i][j] = c[i][j];
        }
    }
}
//a ^ x % mod 
void power_mod(double a[][N], int x, int n) {
    memset(Mat, 0, sizeof(Mat));
    for ( int i=0; i<n; i++) Mat[i][i] = 1;
    while (x != 0) {
        if (x & 1) product_mod(Mat, a, n);
        product_mod(a, a, n);
        x >>= 1;
    }
}
double a[N][N];
int main(int argc, char const *argv[])
{
    int n;
    while (~scanf("%d%lf",&n, &p)){
        for (int i = 1; i <= n; i ++){
            scanf("%d", &num[i]);
        }
        sort(num + 1, num + n + 1);
        n = unique(num + 1, num + n + 1) - (num + 1);
        double ans = 1;
        num[0] = 0;
        for (int i = 1; i <= n; i ++){
            a[0][0] = p;a[0][1] = 1-p;
            a[1][0] = 1;a[1][1] = 0;
            power_mod(a,num[i] - num[i-1] - 1,2);
            ans *= (1 - Mat[0][0]);
            //cout << Mat[0][0] << &#39; &#39; << ans << endl;
        }
        printf("%.7fn",ans);
    }
    return 0;
}

HDU 2604 Queuing

题意：

求2个字母f和m构成的长度为m的序列中不含fmf以及fff的种数。

这题数据太水可以暴力，不过这个也是一个可以矩阵优化DP的题目。 

推出来的DP转移方程为dp[i] = dp[i-1] + dp[i-3] + dp[i-4] 

具体来说就是，当第i位为m的时候前i-1位只要满足条件就能实现了。当第i位为f的时候，就需要分情况讨论了，当第i-1位为m的时候，i-2不能为f，否则出现fmf的情况，那么就是说i-2必须是m，才能够实现，就是dp[i-3] * 1,（表示i-2位只能取m）。然后当第i-1位为f的时候，i-2也只能是m，并且i-3也只能是m，所以最后的几位是mmff，也就是这种情况的解为dp[i-4] * 1(表示i-3只能取一位，而且i-2，i-1都只有一种情况)。最终得出来dp[i] = dp[i-1] + dp[i-3] + dp[i-4]。 

而且这个还是一个线性转移，一维的考虑用矩阵进行转移 

| 1 0 1 1 |   |F[n-1]|   |F[n] | 

| 1 0 0 0 |   |F[n-2]|   |F[n-1]| 

| 0 1 0 0 | * |F[n-3]| = |F[n-2]| 

| 0 0 1 0 |   |F[n-4]|   |F[n-3]|

代码：

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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
int num[12];
#define N 10
int Mat[N][N];
void product_mod(int a[][N], int b[][N], int n,int mod) {
    int c[N][N] = {};
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k ++) {
                c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            a[i][j] = c[i][j];
        }
    }
}
//a ^ x % mod 
void power_mod(int a[][N], int x, int n, int mod) {
    memset(Mat, 0, sizeof(Mat));
    for (int i = 0; i < n; i ++) Mat[i][i] = 1;
    while (x != 0) {
        if (x & 1) product_mod(Mat, a, n, mod);
        product_mod(a, a, n, mod);
        x >>= 1;
    }
}
int A[N][N];
int main(int argc, char const *argv[])
{
    int n,m;
    while (~scanf("%d%d",&n, &m)){
        int mod = m;
        memset(A, 0, sizeof(A));
        A[0][0] = 1;A[0][2] = 1; A[0][3] = 1;
        A[1][0] = 1;A[2][1] = 1; A[3][2] = 1;
        num[1] = 2;
        num[2] = 4;
        num[3] = 6;
        num[4] = 9;
        if (n <= 4){
            printf("%dn", num[n] % mod);
        }else {
            //cout << "n = " << n << endl;
            power_mod(A, n - 4, 4, mod);
            //cout << a[0][0] << ' ' << a[0][1] << ' ' << a[0][2] << ' ' << a[0][3] << endl;
            int ans = Mat[0][0] * num[4] + Mat[0][1] * num[3] + Mat[0][2] * num[2] +
                Mat[0][3] * num[1];
            ans %= mod;
            printf("%dn", ans);
        }
    }
    return 0;
}

HDU 2294 Pendant</span>

差不多的转移方程，只是矩阵的大小有改变。

dp[i][j]=dp[i-1][j]*j+dp[i-1][j-1]*(k-j+1)   

dp[i][j]表示由j种不同的珠子组成长度为i的吊链的方法数

　

因为我们是朋友，所以你可以使用我的文字，但请注明出处：http://alwa.info

Posted on Edited on

http://acm.hdu.edu.cn/contests/contest_show.php?cid=521 

做的杭电的回放，比赛的时候过了4道题，然后1005正在写，写不完了T_T，然后1002的DFS我们没敢敲，其实是有时间的。

A题

求解文本里面多少个doge不区分大小写。直接水,交上去的时候少复制了一行

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
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <utility>
#include <string>
#include <iostream>
using namespace std;
#define LL long long
string line;
LL ans = 0;
void work()
{
    for (int i = 0; i < line.length(); i ++) {
        if (line[i] >= 'A' && line[i] <= 'Z') line[i] = line[i] - &#39;A&#39; + &#39;a&#39;;
    }
    for (int i = 3; i < line.length(); i ++) {
        if (line[i] == 'e' && line[i-1] == 'g' && line[i-2] == 'o' && line[i-3] == &#39;d&#39;) ans ++;
    }
}
int main()
{
    ans = 0;
    while (cin >> line) {
        work();
    }
    cout << ans << endl;
    return 0;
}

B题

DFS+剪枝就能过，赛后也写了好久才AC的，主要是DFS的时候你得剪枝，剪枝还是很好想的，两个剪枝，一个是当前的时间+remain*edge>deadline必然是不行的，一个当前时间+remain*edge>ans这也是不要继续做的。_主要是dfs的时候你判定一定要写在外面判定好了return完了再进行dfs啊之类的操作，不然会TLE，可能这道题目就是卡你dfs的姿势吧_

#include 
#include 
#include 
#include 
using namespace std;
int n;
int d[44][44];
int dead[44];
bool vis[44];
void floyd(){
    for (int k = 1; k <= n; k ++){
        for (int i = 1; i <= n; i ++){
            for (int j = 1; j <= n; j ++){
                if (d[i][j] > d[i][k] + d[k][j]){
                    d[i][j] = d[i][k] + d[k][j];
                }
            }
        }
    }
}
int ans = 1e9;
void dfs(int src, int sumtime,int curtime,int remain){
    if (sumtime >= ans) return;
    if (remain == 0) {
        ans = min(ans,sumtime);
        return;
    }
    //把下面这个for放到里面去判定，就会TLE
    for (int i = 1; i <= n; i ++){
        if (!vis[i] && curtime + d[src][i] > dead[i]){
                return;
        }
    }
    for (int i = 1; i <= n; i ++){
        if (!vis[i] && curtime + d[src][i] > dead[i]){
            return;
        }
        if (!vis[i]){
            if (sumtime + remain * d[src][i] >= ans){
                continue;
            }
            vis[i] = 1;
            //cout << src << ' ' << i << ' ' << sumtime << ' ' << curtime << ' ' << remain << endl;
            dfs(i, sumtime + remain * d[src][i], d[src][i] + curtime, remain - 1);
            vis[i] = 0;
        }
    }
}
int main(int argc, char const *argv[])
{
    while (~scanf("%d", &n)){
        memset(vis, 0, sizeof(vis));
        for (int i = 1; i <= n; i ++){
            for (int j = 1; j <= n; j ++){
                scanf("%d", &d[i][j]);
            }
        }
        for (int i = 2; i <= n; i ++){
            scanf("%d", &dead[i]);
        }
        floyd();
        // for (int i = 1; i <= n; i ++){
        //     for (int j = 1; j <= n; j ++){
        //         printf("%d ", d[i][j]);
        //     }cout << endl;
        // }cout << endl;
        ans = 1e9;vis[1] = 1;
        dfs(1,0,0,n-1);
        if (ans == 1e9) printf("-1n");
        else printf("%dn", ans);
    }
    return 0;
}

C题

蘑菇题，题目写的很凌乱，其实就是求一个最短路，一个是z数组得开到1e6才行，一个是需要long long

#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define maxn 1111
#define maxx 1000010
ll x[maxx],y[maxx],z[maxx];
int c[maxn][maxn],n,m;
void init(){
    z[0] = (x[0] * 90123 + y[0]) % 8475871 + 1;
    z[1] = (x[1] * 90123 + y[1]) % 8475871 + 1;
    for (int i = 2; i <= n * n; i ++){
        x[i] = (12345 + x[i-1] * 23456 + x[i-2] * 34567 + x[i-1] * x[i-2] * 45678)  % 5837501; 
        y[i] = (56789 + y[i-1] * 67890 + y[i-2] * 78901 + y[i-1] * y[i-2] * 89012)  %  9860381; 
        z[i] = (x[i] * 90123 + y[i]) % 8475871 + 1;
    }
    for (int i = 0; i < n; i ++){
        for (int j = 0; j < n; j ++){
            if (i == j) c[i][j] = 0;
            else c[i][j] = z[i * n + j];
        }
    } 
}
ll dis[maxn];
bool vis[maxn];
ll inf = 1e18;
int spfa(int st) {
    for (int i = 0; i <= n; i++) {
        dis[i] = inf;
        vis[i] = false;
    }
    vis[st] = true;
    dis[st] = 0;
    queue Q;
    Q.push(st);
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        vis[u] = false;
        for (int i = 0; i < n; i ++) {
            if (dis[u] + c[u][i] < dis[i]) {
                dis[i] = dis[u] + c[u][i];
                if (!vis[i]) {
                    vis[i] = true;
                    Q.push(i);
                }
            }
        }
    }
    int ans = 1e9;
    //cout << m << endl;
    for (int i = 1; i < n; i ++){
        dis[i] %= (long long)m;
      //  cout << dis[i] << endl;
        ans = min(ans,(int)(dis[i]));
    }
    return ans;
}
int main(){
    while (~scanf("%d%d", &n, &m)){
        cin >> x[0] >> x[1] >> y[0] >> y[1];
        init();
        cout << spfa(0) << endl;
    }
}

D题

一开始我用dfs做的，竟然栈溢出了，赛后才知道可以改成非递归的dfs。不过队友很给力，随机了几个函数，然后就搞过去了。其实就是爆搜，只是变成for循环了。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
template  inline T Max(T a, T b) {return a>b?a:b;}
#define MAXN 500005
int N, a[MAXN], len;
bool vis[MAXN];
void init()
{
    fill(a, a + MAXN, -1);
    a[0] = 0;
    a[1] = 0;
    a[2] = 0;
    len = 3;
    memset(vis, 0, sizeof(vis));
    for (int i = 3; i <= 500000; i ++) {
        int x = (Max(a[i-2], a[i-3]));
        x = Max(x, a[i-1]);
        int flag = 0;
        for (int j = 0; j < 26; j ++) {
            int now = (x + j) % 26;
            int tmp = a[i-3] * 26 * 26 * 26 + a[i-2] * 26 * 26 + a[i-1] * 26 + now;
            if (!vis[tmp]) {
                vis[tmp] = true;
                flag = 1;
                a[i] = now;
                len ++;
                break;
            }
        }
        if (flag == 0) {
            break;
        }
    }
}
void work()
{
    if (len >= N) {
        for (int i = 0; i < N; i ++) {
            printf("%c", (char)(a[i] + 'a'));
        }
        printf("n");
    } else {
        printf("Impossiblen");
    }
}
int main()
{
    init();
    while (scanf("%d", &N) != EOF) {
        work();
    }
    return 0;
}

Posted on Edited on

题意

给出一些牛棚，开始牛棚边有一些牛，牛棚之间有路相连，走一条路会花费固定的时间。牛在牛棚边吃草，下雨时牛得躲进牛棚，每个牛棚容量有限。

求：在所有牛都能进牛棚时最少需要多少时间。

如果知道了时间time，则如果两个牛棚之间所需的最少时间<=time，每个牛棚拆成两点x1和x2。如果两个牛棚a和b之间可以相连,则ax1连ax2，容量为无穷（因为路是无限大的，可以容纳任意多的牛）。s->x1,容量为每个牛棚容量为牛棚的牛数量，x2->t，容量为每个牛棚的容量。

一定要把每个点拆成两个点的。如果直接连原图中的点，是不对的。举个例子:1->2->3, 边长度都为1，则1到3是2。如果枚举ans等于1是，会产生1->2,2->3合法，则最后1也可以到3了，这是错的。

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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
/* From: Lich_Amnesia
 * Time: 2014-07-05 14:59:19
 *
 *
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
using namespace std;
typedef long long ll;
long long INF = 1e17;
int inf = 1e9;
typedef pair <int,int> P;
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define mp make_pair
#define print() cout<<"--------"<<endl
#define maxn 500
//点很容易开少！！！

struct Edge{
	int to,cap,flow;
	Edge(){}
	Edge(int a,int b,int c){
		to = a;
		cap = b;
		flow = c;
	}
};

struct Dinic{
	int n,m,s,t; // 结点数，边数（包括反向弧），源点编号，汇点编号
	vector<Edge> edg; // 边表 edg[e]和edg[e^1]互为反向弧
	vector<int> g[maxn];//邻接表，g[i][j]表示结点i的第j条边在e数组的序号
	bool vis[maxn];//bfs使用
	int d[maxn];//从起点到i的距离，相当于level数组
	int cur[maxn];//当前弧下标

	void init(int N){
		this->n = N;
		edg.clear();
		for (int i = 0; i <= n; i ++){
			g[i].clear();
		}
		memset(d,0,sizeof(d));
	}

	void addEdge(int from,int to,int cap){
		edg.pb(Edge(to,cap,0));
		edg.pb(Edge(from,0,0));
		m = edg.size();
		g[from].pb(m - 2);
		g[to].pb(m - 1);
	}

	bool bfs(){
		memset(vis,0,sizeof(vis));
		queue<int> q;
		q.push(s);
		d[s] = 0;
		vis[s] = 1;
		while (!q.empty()){
			int u = q.front();q.pop();
			for (int i = 0; i < g[u].size(); i ++){
				Edge& e = edg[g[u][i]];
				if (!vis[e.to] && e.cap > e.flow){ // 只考虑残量网络中的弧
					vis[e.to] = 1;
					d[e.to] = d[u] + 1;
					q.push(e.to);
				}
			}
		}
		return vis[t];
	}

	int dfs(int u,int a){
		if (u == t || a == 0) return a;
		int flow = 0, f;
		for (int& i = cur[u]; i < g[u].size(); i ++){//从上次考虑的弧
			Edge& e = edg[g[u][i]];
			if (d[u] + 1 == d[e.to] && 
					(f = dfs(e.to, min(a,e.cap - e.flow))) > 0){
				e.flow += f;
				edg[g[u][i]^1].flow -= f;
				flow += f;
				a -= f;
				if (a == 0) break;
			}
		}
		return flow;
	}

	int maxFlow(int s,int t){
		this->s = s;
		this->t = t;
		int flow = 0;
		while (bfs()){
			memset(cur, 0, sizeof(cur));
			flow += dfs(s, inf);
		}
		return flow;
	}
}G;

#define maxp 500
ll maps[maxp][maxp];
int n,m;
int c[maxp],w[maxp];
void floyd(){
	for (int k = 1; k <= n; k ++){
		for (int i = 1; i <= n; i ++){
			for (int j = 1; j <= n; j ++){
				if (maps[i][k] != INF && maps[k][j] != INF){
					maps[i][j] = min(maps[i][j], maps[i][k] + maps[k][j]);
				}
			}
		}
	}
}

int sum;
bool ok(ll mid){
	G.init(2 * n + 10);
	int st = 2 * n + 1,ed = 2 * n + 2;
	for (int i = 1; i <= n; i ++){
		G.addEdge(st, i, c[i]);
	}
	for (int i = 1; i <= n; i ++){
		G.addEdge(i + n, ed, w[i]);
	}
	for (int i = 1; i <= n; i ++){
		for (int j = 1; j <= n; j ++){
			if (maps[i][j] <= mid){
				G.addEdge(i, j + n, inf);
			}
		}
	}
	return sum == G.maxFlow(st,ed);
	//cout << "ret = " << ret << endl;
}

int main(){
	//cout << INF << endl;
	while (~scanf("%d%d", &n, &m)){
		sum = 0;
		for (int i = 1; i <= n; i ++){
			scanf("%d%d", &c[i], &w[i]);
			sum += c[i];
		}
		for (int i = 1; i <= n; i ++){
			for (int j = 1; j <= n; j ++){
				maps[i][j] = INF;
			}
		}
		//fill(maps, maps + (n + 2) * (n + 2), INF); 
		for (int i = 1; i <= n; i ++) maps[i][i] = 0;
		int u,v,len;
		ll le = 0,ri = 0;
		for (int i = 1; i <= m; i ++){
			scanf("%d%d%d", &u, &v, &len);
			ri += len;
			if (maps[u][v] > len) maps[u][v] = maps[v][u] = len;
		}
		floyd();
		/*for (int i = 1; i <= n; i ++){
			for (int j = 1; j <= n; j ++){
				cout << maps[i][j] << &#39; &#39;;
			}cout << endl;
		}*/	
		//cout << ri << endl;
		ll ans = -1;
		//ri += 1;
		while (le <= ri){
			ll mid = MID(le,ri);
			//cout << le << &#39; &#39; << mid << &#39; &#39; << ri << endl;
			if (ok(mid)){
				ri = mid - 1;
				ans = mid;
			}else {
				le = mid + 1;
			}
		}
		printf("%lldn", ans);
	}
	return 0;
}

Posted on Edited on

参考了：Comzyh博客的网络流算法

增广路

以最大流为例子，考虑求最大流。

首先，假如所有边上的流量都没有超过容量(不大于容量)，那么就把这一组流量，或者说，这个流，称为一个可行流。一个最简单的例子就是，零流，即所有的流量都是0的流。

我们就从这个零流开始考虑，假如有这么一条路，这条路从源点开始一直一段一段的连到了汇点，并且，这条路上的每一段都满足流量<容量，注意，是严格的<,而不是<=。那么，我们一定能找到这条路上的每一段的(容量-流量)的值当中的最小值minCap。我们把这条路上每一段的流量都加上这个minCap，一定可以保证这个流依然是可行流，这是显然的。

这样我们就找到了一个更大的流，他的流量是之前的流量加上minCap，这个就是增广路。

不断地从起点开始寻找增广路，每次都对其进行增广。直到源点汇点不连通，也就是找不到增广路。这个时候当前的流量就是最大流。

反向弧

一开始对反向弧是什么，以及有什么作用完全不是很懂。

看了comzyh的博客少许理解。现在来解释下。

对于最大流。每次进行建图的时候，总是需要建立一条正向边以及一条反向边。对于每次的增广，你需要做的是在图上的残量网络上首先修改的cap值把cap[u,v]减去minCap（这是正向的），然后对于的cap把cap[v,u]加上minCap（这是逆向的）。这样就表示正向边的容量减小了，反向边的容量增加了。这样做有什么好处呢？

举一个例子。

1
2
3
4
5
6
7
8
一个图,(请自行画图),描述(u -> v, 流量)，6个顶点，1为源点，6为汇点。  
1 -> 2  2  
1 -> 3  2  
2 -> 4  2  
3 -> 4  2  
2 -> 5  2  
5 -> 6  2  
4 -> 6  2

首先不考虑反向弧。

现在我们不断地从s点开始寻找增广路，每次都进行增广。假设我们每次更新残余网络只更新正向弧流量，不更新反向弧的流量。

我们找到了一条增广路：1 -> 2 -> 4 -> 6，minCap是2，增广路流量为2。

现在开始找第二条增广路：1 -> 3 -> 4找不下去了。发现这个残余网路已经不能使得s-t连通了，所以说2就是最大流。

可是实际上的最大流为4，并不是2。

仔细想想为什么会出现这样的问题。因为我们没能给程序反悔的机会，也就是说，我们增广路的时候也许并不是最终的流的形式，我们也许需要修改的。

于是就出现了反向边的概念。每条边都有它的反向边，并且反向边也有它的容量。

就是说每次增广路的时候，更新残余网络不仅减少正向弧容量，还增加反向弧的容量。

怎么说呢，对于刚刚的例子：1 -> 2 -> 4 -> 6找到这条增广路的时候，把相应的每条正向边容量减小。反向边容量增加。然后可以再绘制一下新的残余网络了。（有助于理解）

现在对于这个图，你第二次增广的时候1 -> 3 -> 4，然后你发现4 -> 2 还有一条容量为2的弧可以跑。这个时候就可以继续流最终实现的增广路就能成为1 -> 3 -> 4 -> 2 -> 5 -> 6并且流量为2。

这个时候最大流就为4，可以再画一遍新的残余网络。

事实上，当我们第二次的增广路走4 -> 2这条反向边的时候，就相当于把2 -> 4这 条正向边已经是用了的流量给”退”了回去，不走2 -> 4 这条路，而改走从2点出发的其他的路也就是2 -> 5。（有人问如果这里没有2 -> 5 怎么办，这时假如没有2 -> 5 这条路的话，最终这条增广路也不会存在，因为他根本不能走到汇点）同时本来在1 -> 2上的流量由1 -> 3 -> 4这条路来”接管”。而最终2->4这条路正向流量2，反向流量2，等于没有流量。

　

因为我们是朋友，所以你可以使用我的文字，但请注明出处：http://alwa.info

Posted on Edited on

题目大意

一些公司共同拥有一个具有n个顶点的网格，给出了一些边，以及边上会有一些公司，问给出一个起点和重终点，求出这个路径经过的公司，就是每条边上都有的公司。

解题思路

很明显的传递闭包。稍微改改floyd就变成传递闭包了。可以解决图中两个点是否有路径可达。

1
2
3
4
5
6
7
void Floyd(){
	for (int k = 1; k <= n; k ++)
		for (int i = 1; i <= n; i ++)
			for (int j = 1; j <= n; j ++){
				map[i][j] = map[i][j] | (map[i][k] & map[k][j]);
			}
}

现在题目还要求我们在转移图的情况的时候，还要传递一些其他的状态，于是可以考虑在map里面加入状态，就可以考虑进行位运算，把字符串压位存进去。

代码

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
/* From: Lich_Amnesia
 * Time: 2014-07-01 16:14:45
 *
 * POJ 2570
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
using namespace std;

const int INF = ~0u>>1;
typedef pair <int,int> P;
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define mp make_pair
#define print() cout<<"--------"<<endl

#define maxn 222
int map[maxn][maxn];
int n;

void Floyd(){
	for (int k = 1; k <= n; k ++)
		for (int i = 1; i <= n; i ++)
			for (int j = 1; j <= n; j ++){
				map[i][j] = map[i][j] | (map[i][k] & map[k][j]);
			}
}

int main(){
	int u,v;
	char s[100];
	while (cin >> n){
		if (n == 0) break;
		memset(map,0,sizeof(map));
		while (scanf("%d%d", &u, &v)){
			if (u == 0 && v == 0) break;
			scanf("%s", s);
			//cout << s << endl;
			for (int i = 0; i < strlen(s); i ++){
				map[u][v] |= (1<<(s[i] - &#39;a&#39;));
			}
		}
		Floyd();
		while (scanf("%d%d", &u, &v)){
			if (u == 0 && v == 0) break;
			if (map[u][v]){
				for (int i = 0; i <= 26; i ++){
					if (map[u][v] & (1 << i)){
						printf("%c", &#39;a&#39; + i);
					}
				}
				puts("");
			}else {
				puts("-");
			}
		}
		puts("");
	}
	return 0;
}

Posted on Edited on

题目大意

一个由0,1组成的数字串，现在告诉你，第i位到第j位的1的个数为奇数还是偶数。

但是告诉你的可能会自相矛盾，现在就是求出最多能有前几个回答是不矛盾的。

解题思路

对于带权并查集，基本都需要进行抑或操作，关系比较多的时候可能需要取模运算，比如说d[i]表示i与i的父亲的关系。d[i] = d[pa[i]] ^ d[i];

此题也是一样，可以把左端点看做是父亲节点，右端点看做是儿子节点，儿子节点向父亲节点连边，边就相当于c[i]。

于是对于某一个值L，假如出现了[L,R1]和[L,R2]这样的情况，那么R1,R2都是指向L的，并且我们可以解出[R1,R2]之间的关系为d[R1] ^ d[R2]。

这样就是如果出现L,R和其他某次出现的相同的时候会出现合并的情况，其他的就不会出现。

所有并查集的操作全都用抑或实现。

对于每个点，你需要先排序，然后离散化，得到离散化后的点再进行操作。

代码

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
/* From: Lich_Amnesia
 * Time: 2014-07-01 09:33:42
 *
 *
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
using namespace std;

const int INF = ~0u>>1;
typedef pair <int,int> P;
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define mp make_pair
#define print() cout<<"--------"<<endl
#define maxn 22222
int pa[maxn],d[maxn];
int l[maxn],r[maxn],x[maxn],c[maxn];

int find(int x){
	if (pa[x] == x) return x;
	int ret = find(pa[x]);
	d[x] ^= d[pa[x]];
	pa[x] = ret;
	return ret;
}

bool Union(int L,int R,int c){
	int l = find(L);
	int r = find(R);
	if (l == r){
		return ((d[L] ^ d[R]) == c);
	}else {
		if (l > r){
			pa[l] = r;
			d[l] = d[L] ^ c ^ d[R]; 
		}else {
			pa[r] = l;
			d[r] = d[R] ^ c ^ d[L];
		}
	}
	return 1;
}

int bin(int l,int r,int va){
	int mid = MID(l,r);
	while (l <= r){
		mid = MID(l,r);
		if (x[mid] == va) return mid;
		else if (x[mid] < va) l = mid + 1;
		else r = mid - 1;
	}
	return -1;
}

int main(){
	char s[15];int n,m;
	scanf("%d%d", &n, &m);
	int cnt = 0;
	for (int i = 0; i < m; i ++){
		scanf("%d%d%s", &l[i], &r[i], s);
		x[cnt ++] = l[i] - 1;
		x[cnt ++] = r[i];
		if (s[0] == 'o') c[i] = 1;
		else c[i] = 0;
	}
	sort(x, x + cnt);
	cnt = unique(x, x + cnt) - x;
	for (int i = 0; i <= maxn; i ++){
		pa[i] = i;
		d[i] = 0;
	}
	for (int i = 0; i < m; i ++){
		int L = bin(0, cnt - 1, l[i] - 1) + 1;
		int R = bin(0, cnt - 1, r[i])  + 1;

		if (Union(L,R,c[i]) == 0){
			printf("%dn", i);
			return 0;
		}
	}
	printf("%dn", m);
	return 0;
}

Posted on Edited on 
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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<time.h>
#include<Windows.h>
/********函数变量声明********/
#define PR_Box printf("■")
#define PR_Gold printf("★")
#define PR_Ag printf("☆")
#define PR_FBird printf("Ю")
#define PR_DBird printf("Ф")
#define PR_Land printf("┳┳┯")
#define PR_Bg_TL printf("╔")
#define PR_Bg_TR printf("╗")
#define PR_Bg_DL printf("╚")
#define PR_Bg_DR printf("╝")
#define PR_Bg_X printf("═")
#define PR_Bg_Y printf("║")
#define PR_Blank printf("  ");
int Grade = 1, C_Gold = 0, C_Ag = 0, Score = 0, Delay_time = 1000,Max_blank=9,Distance=18;
//Grade 游戏等级 
//Score 分数 
//Max_blank 上下两个烟囱之间的最大距离   
//Distance  左右两个烟囱之间的距离
struct Birds//小鸟的结构体
{
	int x, y;//小鸟的位置
	int condition;//此变量未用
};
Birds *Bird = (Birds*)malloc(sizeof(Birds));//给小鸟指针分配空间
struct Bg//烟囱的结构体--循环双向链表
{
	int x, y;//上烟囱的左下角砖块的坐标
	int l_blank;//上相两个烟囱之间的距离
	int reward[9];
	Bg *pri;//前指针-指向前一个结点
	Bg *next;//后指针-指向后一个结点
};
Bg *Bg1 = new Bg[sizeof(Bg)];//将一个烟囱结点设置成全局变量
void Position(int x, int y)//将光标移动到X,Y坐标处
{
	COORD pos = { x - 1, y - 1 };
	HANDLE Out = GetStdHandle(STD_OUTPUT_HANDLE);
	SetConsoleCursorPosition(Out, pos);
}
void CreatBird()//创建小鸟
{
	Bird->x=41;//小鸟的坐标
	Bird->y=10;
	Bird->condition =0;
}
void CreatBg()//创建数据结构为循环双向链表的烟囱
{
	Bg *Bg2 = (Bg*)malloc(sizeof(Bg));

	Bg1->x=90;Bg1->y =8;
	Bg2->x=Bg1->x+Distance;Bg2->y =9;

	Bg1->l_blank =Max_blank-Grade;
	Bg2->l_blank =Max_blank-Grade;

    Bg1->next=Bg2;
	Bg1->pri=Bg2;
	Bg2->next=Bg1;
	Bg2->pri=Bg1;
}
void InsertBg(Bg *p)//创建一个结点插入到传入结点之前。循环双向链表的插入
{int temp;
Bg *Bgs = (Bg*)malloc(sizeof(Bg));
Bgs->x=p->pri->x+Distance;
Bgs->l_blank =Max_blank-Grade;
srand((int)time(0));//将系统时间作为产生随机数的种子
temp=rand();//产生随机数
if(temp%2==0)//当随机数%==2时，烟囱口向下移动
{  if((temp%4+p->pri->y+Max_blank-Grade)<21)//检测是否存在向下移动的可行性
Bgs->y=p->pri->y+temp%4;//若有则向下移动temp%4个单位
else
Bgs->y=p->pri->y;//若无，则不动
}
else//反之亦然
{
	if((p->pri->y-temp%4)>2)
		Bgs->y=p->pri->y-temp%4;
	else
		Bgs->y=p->pri->y;
}

Bgs->pri=p->pri;//循环链表指向
Bgs->next =p;
p->pri->next=Bgs;
p->pri =Bgs;
}
void Check_Bg(Bg *q)//检查是否有烟囱超出屏幕，若有超出，则移动到屏幕右侧。
{ Bg *p=q;int i=0,temp;
while(++i<=5)//注意烟囱只有5个，时来回循环移动的
{  if(p->x>-4)//若有烟囱超出
p=p->next;
else
{   srand((int)time(0));
temp=rand();
if(temp%2==0)//++
{  if((temp%4+p->y+Max_blank-Grade)<21)
p->y=p->y+temp%4;
else
p->y=p->y;
p->x=p->pri->x+Distance;//将烟囱移动到前一结点的右侧+Distance的单位
p->l_blank=Max_blank-Grade;//计算上下两个烟囱的距离
}
else//反之亦然
{
	if((p->y-temp%4)>2)
		p->y=p->y-temp%4;
	else
		p->y=p->y;
	p->x=p->pri->x+Distance;
	p->l_blank=Max_blank-Grade;
}
}

}

}
void Loop_Bg(Bg *q)//烟囱单向循环移动
{
	Bg *p=q;int i=0;
	while(++i<=5)
	{p->x=p->x-1;
	p=p->next ;
	if(Bird->x==p->x)//每经过一个烟囱，加一分
	{Score+=1;
    if(Score%4==0&&Grade<4)//烟囱
		Grade++;
	}
	}
}
void Prt_Bg(Bg *q)//画烟囱----较冗余的代码
{  Bg *p=q;int i=0,k,j;
while(++i<=5)
{  if(p->x>0&&p->x<=78)
{ for(k=2;k<p->y;k++)//画出上烟囱上半部分
{   Position(p->x+1,k);
PR_Box;PR_Box;PR_Blank;//输出两个格子，输出空格，清除原来余影
}
Position(p->x,p->y);//画出上烟囱下半部分
PR_Box;PR_Box;PR_Box;PR_Blank;//输出三个格子，输出空格，清除原来余影
Position(p->x,p->y+p->l_blank);//画出下烟囱上半部分
PR_Box;PR_Box;PR_Box;PR_Blank;//输出三个格子，输出空格，清除原来余影
k=k+p->l_blank+1;
for(k;k<=22;k++)//画出下烟囱下半部分
{Position(p->x+1,k);
PR_Box;PR_Box;PR_Blank;//输出两个格子，输出空格，清除原来余影
}
Position(p->x,23);//输出地下的线
for(k=1;k<Distance/3-2;k++)
PR_Land;

}
p=p->next;
if(p->x==0)
{  for(j=2;j<p->y;j++)
{  Position(p->x+1,j);
PR_Blank;PR_Blank;
}
Position(p->x+1,p->y);
PR_Blank;PR_Blank;PR_Blank;
Position(p->x+1,p->y+Max_blank-Grade);
PR_Blank;PR_Blank;PR_Blank;
j=j+Max_blank-Grade+1;
for(j;j<=22;j++)
{Position(p->x+1,j);
PR_Blank;PR_Blank;
}
}
}

}

void PrtBg()//画上下两条线
{ int i;
Position(1,1);PR_Bg_TL;
Position(79,1);PR_Bg_TR;
Position(1,24);PR_Bg_DL;
Position(79,24);PR_Bg_DR;
for(i=3;i<=78;i+=2)
{ Position(i,1);PR_Bg_X;
Position(i,24);PR_Bg_X;
}
/*for(i=2;i<=23;i++)
{ Position(1,i);PR_Bg_Y;printf("%d",i-1);
Position(79,i);PR_Bg_Y;
}*/
}
void PrtBird()//画鸟
{ Position(Bird->x,Bird->y-1);//清除原来屏幕上面的鸟
PR_Blank;
Position(Bird->x,Bird->y);//画新鸟
PR_FBird;
Position(38,2);
printf("Score:%d",Score);//输出得分
}
int CheckYN(Bg *q)//检查是否撞壁
{ Bg *p=q;int i=0;
while(++i<=5)
{ if(Bird->y>23)//鸟是否落地
return 0;
if(Bird->x==p->x&&Bird->y<=p->y)//是否撞到上烟囱左侧
return 0;
if((Bird->x==p->x||Bird->x==p->x+1||Bird->x==p->x+2)&&Bird->y==p->y)//是否撞到上烟囱下侧
return 0;
if(Bird->x==p->x&&Bird->y>p->y+p->l_blank)//是否撞到下烟囱左侧
return 0;
if((Bird->x==p->x||Bird->x==p->x+1||Bird->x==p->x+2)&&Bird->y==p->y+p->l_blank)//是否撞到上烟囱上侧
return 0;
p=p->next;
}
return 1;
}

void Prtfirst()
{
	system("pause");
	Position(1,1);
	int i=0;
	while(i++<40*25)
		PR_Blank;
}
int main()
{
	int i=0;char ch;
	Prtfirst();//开始屏幕

	PrtBg();//画上下两边的框框
	CreatBg();//创建循环双向链表烟囱
	InsertBg(Bg1);//给循环双向链表中插入一个烟囱结点
	InsertBg(Bg1);//给循环双向链表中插入一个烟囱结点
	InsertBg(Bg1);//给循环双向链表中插入一个烟囱结点
	CreatBird();//创造小鸟
	while(1)
	{
		if(!CheckYN(Bg1))//检查鸟是否碰壁
			break;//若碰壁，则退出
		Check_Bg(Bg1);//检查是否有烟囱X坐标<0
		Prt_Bg(Bg1);//画背景烟囱
		PrtBird();//画小鸟
		Loop_Bg(Bg1);//背景烟囱单项循环
		Bird->y=Bird->y+1;
		if(GetAsyncKeyState(VK_UP))//检测是否有按键
		{   
			Position(Bird->x,Bird->y-1);
			PR_Blank;//在屏幕上清除原小鸟
			Bird->y=Bird->y-4;//鸟的位置上升4个长度
		}
		while(i++<500);
		{ Sleep(100);
		}
		i=0;
    }
	Position(38,10);
	printf("You Lost!");
    Position(1,25);
	system("pause");

}
// 1 2 3 4 5 6 7 8  10        15        20        25        30        35    38
//══════════════════════════════════════
//1    ■■            ■■
//2    ■■            ■■
//3    ■■            ■■
//4    ■■            ■■
//5    ■■            ■■
//6    ■■            ■■
//7   ■■■           ■■
//8                    ■■
//9                    ■■
//10    Ю            ■■■
//11
//12  ■■■
//13   ■■
//14   ■■
//15   ■■           ■■■
//16   ■■            ■■
//17   ■■    Ф      ■■
//18   ■■            ■■
//19   ■■            ■■
//20   ■■            ■■
//21   ■■            ■■
//22┳┳┯┳┳┯┳┳┯┳┳┯┳┳┯┳┳┯┳┳┯┳┳┯┳┳┯┳┳┯┳┳┯┳┳┯┳
//══════════════════════════════════════

Posted on Edited on

问题

N种物品和容量为V的背包，若第i种物品大小(重量)为we[i]，价值为va[i],共有n[i]件,怎样才能使背包内物品总重量最大

Read more »

Posted on Edited on

1、笔记本有无线网卡且支持 虚拟WIFI

2、按win+R键，打开运行后输入cmd回车（也就是搜索程序和文件那个框框）

3、输入netsh wlan set hostednetwork mode=allow ssid=mywifi key=12345678 这个设置无线名称(mywifi)和链接密码 等有提示设置成功出现再关闭

4、同样按上面的步骤cmd中输入netsh wlan start hostednetwork 启动wifi 启动承载网络出现再关闭

5、这个时候再控制面板中找到网络和共享中心 点击进入

6、左侧点击”更改适配器设置”会弹出网络连接界面 里面有本地连接 无线连接 无线连接2（microsoft virutal wifi miniport 这个无线连接2就是wifi热点啦） 右击他点属性，找到internet TCP/IP协议4 双击进入设置IP 地址为192.168.0.1 掩码 255.255.255.0 关闭 确定

7、找到本地连接 （用路由器网线上网的那个也就是） 同样右击 属性—-点共享选项卡—允许其他网络用户通过次。。。前面打钩———家庭网络选中无线网络2（就是选wifi热点刚刚设置那个），确定。

8，OK，这样基本电脑端设置就OK了，然后进行手机设置

9、连接SSID mywifi 连接 输入密码 12345678，连接上

10、全部搞定

11、如果是宽带连接 不是路由器上网把本地连接的操作的换到宽带连接（拨号那个）设置 主要讲链接后断线的问题 一般是手机 WLAN 设置里面 休眠状态 把里面改成永不休眠就可以 另外 笔记本也要把电池的模式改成 非省电状态（排除此原因 因为老婆的笔记本测试下来 距离和稳定度可以 但手机还是要设置的） 这样就不会频繁断线了 另外 笔记本驱动不最新 可能遇到 无法承载的问题 这个时候更新下 笔记本无线网卡驱动 重启 基本可以解决该问题 如果还是不行的话 cmd打开后 输入 netsh wlan show drivers 看承载网络后面是是不是 ：是 是是的话OK 否的话就悲剧 不支持

Posted on Edited on

A POJ 1182 食物链的

D POJ 1740 男人八题

A

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
#define maxn 50010
int parent[maxn],dis[maxn];
int n;
void init()
{
    for(int i=0;i<=n;i++)
    {
        parent[i]=i;
        dis[i]=0;
    }
}

int find(int x)
{
    if(parent[x]==x) return x;
    int tmp=find(parent[x]);
    dis[x]=(dis[x]+dis[parent[x]]+3)%3;
    return parent[x]=tmp;
}

void Union(int R1,int R2,int d)
{
    int r1=find(R1),r2=find(R2);
    parent[r2]=r1;
    dis[r2]=(dis[R1]-d+3-dis[R2])%3;
    //dis[R1]=(dis[R2]+d)%3;
}

int main(){
    int k,a,b,d,A,B;
    int T;
    scanf("%d",&T);
    while (T--){
        scanf("%d%d", &n, &k);
        int ans=0;
        init();
        for(int i=0;i<k;i++)
        {
            scanf("%d%d%d",&d,&a,&b);
            if(a>n||b>n) {ans++;continue;}
            if(a==b&&d==2) {ans++;continue;}
            A=find(a);
            B=find(b);
            d--;
            if(A==B){
                if(d==0&&dis[a]!=dis[b])
                    ans++;
                if(d==1&&(dis[a]-dis[b]+3)%3!=1)
                    ans++;
            }
            else{
                Union(a,b,d);
            }
        }
        printf("%dn",ans);
    }
    return 0;
}

B

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
//906MS水过
//好多地方可以优化比如数组大小最大1600/2基本就够了
//其实是可以二维的

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
using namespace std;

inline int f(int a,int b,int c){
	double p = (a +b+c)/2.0;
	return (int)(100.0*sqrt(p*(p-a)*(p-b)*(p-c)));
}

inline bool check(int a,int b,int c){
	if (a + b > c && a + c > b && b + c > a) return true;
	else return false; 
}
int ans = 0;
int n,num[45],to[45];
void dfs(int id,int a,int b,int c){
	if (id == n) {
		if (check(a,b,c)) {
			ans = max(ans,f(a,b,c));
		}
		return;
	}
	if (a + to[n - 1] - to[id] + b + num[id] < c) return;
	if (a + to[n - 1] - to[id] + c + num[id] < b) return;
	if (c + to[n - 1] - to[id] + b + num[id] < a) return;
	if (a > to[n - 1] / 2) return;
	if (b > to[n - 1] / 2) return;
	if (c > to[n - 1] / 2) return;
 	dfs(id + 1,num[id] + a, b, c);
	dfs(id + 1,a, num[id] + b, c);
	dfs(id + 1,a, b, num[id] + c);
}

int dp[2][1655][1655];
int main()
{
	while (~scanf("%d",&n) && n){
		ans = -1;
		for (int i = 1; i <= n; i ++){
			scanf("%d", &num[i]);
			if (i == 0) to[0] = num[0];
			else to[i] = to[i - 1] + num[i];
		}
		sort(num,num + n);
		//dfs(0,0,0,0);

		memset(dp,-1,sizeof(dp));
		dp[0][0][0] = 0;
		for (int i = 1; i <= n; i ++){
			for (int j = 0; j <= to[i]; j ++){
				for (int k = 0; k <= to[i]; k ++){
					if (j - num[i] >= 0){
						if (dp[(i + 1) % 2][j - num[i]][k] != -1){
							if (check(j,k,to[i] - j - k))
								dp[i % 2][j][k] = max(dp[i % 2][j][k],f(j,k,to[i]-j-k));
							else dp[i % 2][j][k] = max(0,dp[i % 2][j][k]);
						}
					}
					if (k - num[i] >= 0){
						if (dp[(i + 1) % 2][j][k - num[i]] != -1){
							if (check(j,k,to[i] - j - k))
								dp[i % 2][j][k] = max(dp[i % 2][j][k],f(j,k,to[i]-j-k));
							else dp[i % 2][j][k] = max(0,dp[i % 2][j][k]);
						}
					}
					if (to[i] - j - k - num[i] >= 0){
						if (dp[(i + 1) % 2][j][k] != -1){
							if (check(j,k,to[i] - j - k))
								dp[i % 2][j][k] = max(dp[i % 2][j][k],f(j,k,to[i]-j-k));
							else dp[i % 2][j][k] = max(0,dp[i % 2][j][k]);
						}
					}
				}
			}
		}
		for (int i = 0; i <= to[n]; i ++)
			for (int j = 0; j <= to[n]; j ++){
				ans = max(dp[n % 2][i][j],ans);
			}
		printf("%dn", ans == 0? -1:ans );
	}
	return 0;
}

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
#define maxn 1010
struct Info{
    int x1,x2,y1,y2,r,g,b;
}p[maxn];

int main(int argc, char const *argv[])
{
    int x,y,n,m;
    while (~scanf("%d%d", &n, &m)){
        for (int i = 0; i < n; i ++){
            scanf("%d%d%d%d%d%d%d",&p[i].x1,&p[i].y1,&p[i].x2,&p[i].y2
                ,&p[i].r,&p[i].g,&p[i].b);
        }

        while(m--){
            scanf("%d%d", &x, &y);
            int r = 255,g = 255,b = 255    ;
            for (int i = n - 1; i >= 0; i --){
                if (p[i].x1 <= x && x <= p[i].x2 && p[i].y1 <= y && y <= p[i].y2){
                    r = p[i].r;
                    g = p[i].g;
                    b = p[i].b;
                    break;
                }
            }
            printf("%d %d %dn", r, g ,b);
        }

    }
    return 0;
}

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
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;

int main()
{
int a[20],n;
    while(~scanf("%d",&n)&&n)
    {
        int k=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        sort(a,a+n);
        for(int i=0;i<n;i+=2)
        if(a[i]==a[i+1]) k++;
        int j=n-2*k;
        if(j==0) printf("Losen");
        else printf("Winn");
    }
    return 0;
}