2018-2019 ACM-ICPC Brazil Subregional Programming Contest

Diposting di | Edited on

传送门

付队！

许老师！

B.Marbles （nim博弈）

题意

一个棋盘n个点,每次可以把一个棋子移动到(x-d,y) or (x,y-d) or (x-d,y-d) 把其中一个棋子移动到(0,0)的人就胜利

问先手能否必胜

思路

我非常喜欢的一题，一开始看到题面第一反应我操nim博弈煞笔题,然后傻逼一样得写了 判断到全部到（0，0)就赢的博弈，后面发现我想错了，我写的是相当于把全部石子取完的博弈，而这题只要把其中一堆石子取完就赢了，所以不正确，还是许老师厉害，把题意转换一下，题目开始是到(0,0)就赢，那什么情况下肯定输呢，那就是到(1,2) (2,1)这种死局的情况，每个人肯定都不想发生这种情况，于是我们就把题目转化成 把石子取到(1,2) （2,1）这种奇异态，而如果一个人面临这种局面那就是稳输的，于是我们把(1,2)这种状态构造成取完，而后面一个人面临一个取完（只有必败态的）时候那他就必输，所以这题就变成把N堆石子取成必输态的NIM博弈了，注意要特判先手直接赢的情况

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int sg[110][110];
int flag[500];
void init(){
    for(int i=1;i<=100;i++)sg[i][0]=sg[0][i]=sg[i][i]=0;
    for(int i=1;i<=100;i++){
        for(int j=1;j<=100;j++){
            if(i==j)continue;
            memset(flag,0,sizeof(flag));
            for(int k=1;k<i;k++)if(k!=j)flag[sg[k][j]]=1;
            for(int k=1;k<j;k++)if(k!=i)flag[sg[i][k]]=1;
            for(int k=1;k<min(i,j);k++)
                if(i-k!=j-k)flag[sg[i-k][j-k]]=1;
            for(int k=0;k<500;k++){
                if(flag[k]==0){sg[i][j]=k;break;}
            }
        }
    }
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    cin>>n;
    init();
    int f=0;
    int ans=0;
    while(n--){
        int a,b;
        cin>>a>>b;
        ans^=sg[a][b];
        if(a==b)f=1;
    }
    if(f||ans)cout<<"Y"<<endl;
    else cout<<"N"<<endl;
    return 0;
}

D.Unraveling Monty Hall（水题）

判断不是1的个数就行，大早上读题读得我怀疑人生

1
2
3
4
5
6
7
8
9
    int n;
    cin>>n;
    int ans=0;
    while(n--){
        int a;cin>>a;ans+=(a==1)?0:1;
    }
    cout<<ans<<endl;
    return 0;
}

E.Enigma (模拟)

题意

给你两个字符串s,t让判断前strlen(t)中的s有多少个是T中没有的

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e2+50;
const ll inf=1e10;
const double eps=1e-5;

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    string s;
    string t;
    cin>>s>>t;int ans=0;
    int len=s.size();int len1=t.size();
    for(int i=0;i<len-len1+1;i++){
        bool flag=1;
        for(int j=0;j<len1;j++)if(t[j]==s[i+j])flag=0;
        ans+=flag;
    }
    cout<<ans<<endl;
    return 0;
}

F.Music Festival (线段树/线段数组) （待补）

题意

有N个舞台(N<10)，第i个舞台有Mi首歌(M总和<1000)，给出每首歌的起始时间s，和终止时间t，以及价值val； 我们听完一首歌可以任意瞬移到另外的舞台，即不考虑时间边界。现在让你选择一种方案，使得每个舞台都至少听了一首歌，求最大价值。

题解

G.Gasoline (二分网络流)

题意

有p个加油站，r个油田，给出每个加油站需要的油以及每个油田库存的油，有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
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e5+50;
const ll inf=1e10;
const ll INF = 1000000000;
const double eps=1e-5;
struct Edge {
  int from, to;
  ll cap, flow;
};

struct Dinic {
  int n, m, s, t;
  vector<Edge> edges;    // 边数的两倍
  vector<int> G[maxn];   // 邻接表，G[i][j]表示结点i的第j条边在e数组中的序号
  bool vis[maxn];         // BFS使用
  int d[maxn];           // 从起点到i的距离
  int cur[maxn];        // 当前弧指针

  void ClearAll(int n) {
    for(int i = 0; i < n; i++) G[i].clear();
    edges.clear();
  }

  void ClearFlow() {
    for(int i = 0; i < edges.size(); i++) edges[i].flow = 0;
  }

  void AddEdge(int from, int to, ll cap) {
    edges.push_back((Edge){from, to, cap, 0});
    edges.push_back((Edge){to, from, 0, 0});
    m = edges.size();
    G[from].push_back(m-2);
    G[to].push_back(m-1);
  }

  bool BFS() {
    memset(vis, 0, sizeof(vis));
    queue<int> Q;
    Q.push(s);
    vis[s] = 1;
    d[s] = 0;
    while(!Q.empty()) {
      int x = Q.front(); Q.pop();
      for(int i = 0; i < G[x].size(); i++) {
        Edge& e = edges[G[x][i]];
        if(!vis[e.to] && e.cap > e.flow) {
          vis[e.to] = 1;
          d[e.to] = d[x] + 1;
          Q.push(e.to);
        }
      }
    }
    return vis[t];
  }

  int DFS(int x, ll a) {
    if(x == t || a == 0) return a;
    int flow = 0, f;
    for(int& i = cur[x]; i < G[x].size(); i++) {
      Edge& e = edges[G[x][i]];
      if(d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap-e.flow))) > 0) {
        e.flow += f;
        edges[G[x][i]^1].flow -= f;
        flow += f;
        a -= f;
        if(a == 0) break;
      }
    }
    return flow;
  }

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

  vector<int> Mincut() { // call this after maxflow
    vector<int> ans;
    for(int i = 0; i < edges.size(); i++) {
      Edge& e = edges[i];
      if(vis[e.from] && !vis[e.to] && e.cap > 0) ans.push_back(i);
    }
    return ans;
  }

  void Reduce() {
    for(int i = 0; i < edges.size(); i++) edges[i].cap -= edges[i].flow;
  }
};

Dinic g;

int a[maxn],b[maxn],u[maxn],v[maxn],w[maxn];
int p,r,c,sum=0;
int S,T;
bool isok(int x){
    g.ClearAll(T+1);
    for(int i=1;i<=p;i++)g.AddEdge(S,i,a[i]);
    for(int i=1;i<=r;i++)g.AddEdge(p+i,T,b[i]);
    for(int i=1;i<=c;i++)if(w[i]<=x)g.AddEdge(u[i],p+v[i],inf);
    ll res=g.Maxflow(S,T);
    if(res==sum)return true;
    else return false;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    cin>>p>>r>>c;
    S=0,T=p+r+1;
    for(int i=1;i<=p;i++)cin>>a[i],sum+=a[i];
    for(int i=1;i<=r;i++)cin>>b[i];
    for(int i=1;i<=c;i++)cin>>u[i]>>v[i]>>w[i];
    int L=0,R=1e7,ans=-1;
    while(L<=R){
        int mid=(L+R)/2;
        if(isok(mid))R=mid-1,ans=mid;
        else L=mid+1;
    }
    if(ans==-1)cout<<-1<<endl;
    else cout<<ans<<endl;
    return 0;
}

I.Switches (模拟)

题意

给定N个灯，以及开始状态。M个开关集合，每次使用一个开关，这个集合的状态会改变。 现在一次按1到M个开关，即1，2，3，…M ,1, 2,… 问第几次会全部关掉。

思路

直接模拟咯，用bitset表示灯的状态

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e5+50;
const ll inf=1e10;
const ll INF = 1000000000;
const double eps=1e-5;
bitset<1010>b[1100],c;

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n,m,k,x;
    cin>>n>>m>>k;
    for(int i=0;i<k;i++)cin>>x,c.set(x);
    for(int i=1;i<=n;i++){
        cin>>k;while(k--)cin>>x,b[i].set(x);
    }
    for(int i=1;i<=n;i++){
        c^=b[i];
        if(c.count()==0){
            cout<<i<<endl;return 0;
        }
    }
    for(int i=1;i<=n;i++){
        c^=b[i];
        if(c.count()==0){
            cout<<i+n<<endl;
            return 0;
        }
    }
    cout<<-1<<endl;
    return 0;
}

L.Subway Lines (树剖) （待补）

题意

给一棵树，询问两条路径上公共点的个数。