题面：http://codeforces.com/contest/787/problems
异常难打的一场cf啊…C题就开始看题解了..D题是线段树建图+Dijkstra…等我以后熟练掌握了线段树再补吧orz
A. The Monster
题意：给定a.b.c.d, 甲在每个$ b + a \cdot i $时刻尖叫, 乙在每个$ d + c \cdot i $时刻尖叫, 问是否存在两者同时尖叫的时刻。
解法：暴力 or 扩展欧几里得
暴力: 跑它个1e7,看是否存在同时尖叫的时刻, 有则输出 否则-1
扩展欧几里得, 相当于解方程
并且x,y都必须为正数
扩展欧几里得的相关知识可以见我另一篇博客
细节见代码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
using namespace std;
void e_gcd(int a, int b, int &gcd, int &x, int &y)
{
if(!b)
{
x = 1; y = 0; gcd = a;
}
else
{
e_gcd(b, a % b, gcd, y, x);
y -= x * (a / b);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int a, b, c, d, g;
int x, y;
cin >> a >> b >> c >> d;
e_gcd(a, -c, g, x, y);
if((d - b) % g)
{
cout << -1 << endl;
return 0;
}
x = x * (d - b) / g;//求出方程的x
//求出最小非负整数x
//需要x和y均大于0
x = x % (-c / g);
if (x < 0)
x += fabs(-c / g);
y = ((d - b) - a * x)/(-c);//求出方程的y
while(y < 0){
x = x + fabs(-c / g);
y = ((d - b) - a * x)/(-c);
}
cout << b + x * a << endl;
return 0;
}
B. Not Afraid
题意：难点可能在读题上面 有n所大学, 每所大学都有一个Ricks和Mortys, 每所学校的这两个人中有一个叛徒, 现在有若干个group, 每个group由这些人中的若干组成, 如果所有的人都是叛徒, 则可能发生危险。问是否会有发生危险的可能。
解法：读入每个组的, 如果不存在同一所大学的两个人都在同一个group, 则可能发生危险。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
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
while(m--)
{
int k; cin >> k;
map<int, int> q;
bool f = 1;
while(k--)
{
int t; cin >> t;
q[t] = 1;
if(q[-t]) f = 0;
}
if(f)
{
cout << "YES" << endl;
return 0;
}
}
cout << "NO" << endl;
return 0;
}
C. Berzerk
或将成为我做的第一道博弈题
题意：有一个n个数组成的环, 第一个数所在的位置是一个洞, 怪兽一开始处于剩下的n-1个位子中的一个。
有两个人玩游戏, 他们每次可以把怪兽顺时针推一定的格数, 两个人各有若干种推法, 第一个将怪兽推进洞的人获胜, 有可能陷入Loop。
现问你不同的人先手, 每个人都选择最佳策略的情况下, 游戏结果是什么。
解法：dp
考虑必败态, 如果现在怪兽已经在1位置, 则现在要推的人处于必败态, 考虑逆向推, 所有能到达这个状态的那个人处于必胜态。
dp[i][j]表示当前位置为i, 轮到j推的状态。
用图的拓扑排序的思路来考虑, 每个状态结点, 我有n种推法, 把之看为出度。
如果当前态是必败态, 那么前一个人能够到达这个下一个人必败态的必然是必胜态。
如果当前态是必赢态, 由于是最佳策略, 前一个人一定不会考虑到达这一步, 所以将出度减1, 当出度为0时, 这个态不管怎么推都是输, 所以是必输态。
由于存在循环, 所以用一个bfs, 每次记录, 如果bfs没有访问到, 那么这个态不是必输也不是必胜, 则必然是一个循环态。
用一个队列模拟, 如果必胜, 前一个出度减1, 如果出度为0, 必输, 加入队列。
如果必输, 前一个结点必胜, 加入结点。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
const int maxn = 1e5 + 10;
using namespace std;
int dp[maxn][2];
//dp[i][j]表示当前怪兽在x点 且轮到j号玩家操作
int deg[maxn][2];//存度数
vector<int> k[2];//存两个人的可走步数
struct node{
int loc, turn, ans;
};
queue<node> Q;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for(int i = 0; i < 2; i++)
{
int t; cin >> t;
k[i].resize(t);
for(auto &idx: k[i])
cin >> idx;
}
for(int i = 0; i < n; i++)
{
deg[i][0] = (int)k[0].size();
deg[i][1] = (int)k[1].size();
}
memset(dp, -1, sizeof(dp));
dp[0][1] = dp[0][0] = 0;
Q.push({0, 0, 0});
Q.push({0, 1, 0});
while(Q.size())
{
node now = Q.front();
Q.pop();
int t = !now.turn;
if(now.ans == 0)//如果当前状态是必输态
{
for(auto idx: k[t])
{
int state = (now.loc + n - idx) % n;
if(dp[state][t] == -1)
{
dp[state][t] = 1;//前一个状态是必赢态
Q.push(node{state, t, 1});
}
}
}
else //如果当前状态是必赢态
{
for(auto idx: k[t])
{
int state = (now.loc + n - idx) % n;
deg[state][t]--;//度数减1 最优策略下不可能选取这一策略
if(deg[state][t] == 0 && dp[state][t] == -1)
{
dp[state][t] = 0;
Q.push(node{state, t, 0});
}
}
}
}
for(int i = 0; i < 2; i++)
{
for(int j = 1; j < n; j++)
{
if(dp[j][i] == - 1)
cout << "Loop ";
else if(dp[j][i] == 0)
cout << "Lose ";
else
cout << "Win ";
}
cout << endl;
}
return 0;
}