Moscow International Workshops 2017. Day 4. Lviv NU Contest, GP of Ukraine

Preface

国庆本以为空的一批结果忙的飞起，好不容易抽时间凑到三个人，结果被 Div2 小登们按在地上摩擦。

B. Card Game

签到，暴力枚举约数即可

#include<cstdio>
#include<iostream>
#include<map>
#define RI register int
#define CI const int&
using namespace std;
int n,m;
int main()
{scanf("%d%d",&n,&m);int mxn=0,mxc=0;map <int,int> cnt;for (RI i=1;i<=m;++i){int x; scanf("%d",&x);mxn=max(mxn,x);mxc=max(mxc,++cnt[x]);}int ways=0;for (RI s=1;s*s<=n;++s){auto check=[&](CI s){if (s>=mxn&&n/s>=mxc) ++ways;};if (n%s!=0) continue;check(s);if (s*s!=n) check(n/s);}return puts(ways==1?"YES":"NO"),0;
}

C. The Most Expensive Gift

队友写的，好像是说根据观察最后可能的周期串长度不会很大，因此可以直接暴枚周期串然后跑序列自动机

#include <bits/stdc++.h>int n;
std::string s;
int nxt[10000][3];std::vector<std::pair<int, int>> try_move(const std::vector<std::pair<int, int>> &cur,int ch
) {std::vector<std::pair<int, int>> res;int p = 0, r = -1, l = cur.size();while(p < l) {// std::cerr << "FUCK: " << cur[p].second << ", " << ch << ", " << nxt[cur[p].second][ch] << char(10);int nx = nxt[cur[p].second][ch];if(nx >= n) break;res.emplace_back(cur[p].first, nx);do p += 1;while(p < l && cur[p].first <= nx);}return res;
}int ans;void dfs(const std::vector<std::pair<int, int>> &cur,int depth
) {if(cur.empty()) return ;ans = std::max(ans, (int)(depth * cur.size() * cur.size()));// std::cerr << "debug cur(" << (int)(depth * cur.size() * cur.size()) << ") = ";// for(auto [l, r]: cur) {//     std::cerr << " [" << l << ", " << r << "]";// }// std::cerr << "\n";if(depth >= 10 && (n / (depth + 1)) * (n / (depth + 1)) * (depth + 1) <= ans) return ;for(int ch = 0; ch < 3; ++ch) dfs(try_move(cur, ch), depth + 1);
}int main(void) {std::ios::sync_with_stdio(false);std::cin >> n;std::cin >> s;int ss[3] = {n, n, n};for(int i = n - 1; i >= 0; --i) {memcpy(nxt[i], ss, sizeof(ss));ss[s[i] - 'a'] = i;}int cnt[3] = {0, 0, 0};for(int i = 0; i < n; ++i) cnt[s[i] - 'a'] += 1;ans = *std::max_element(cnt, cnt + 3);ans = ans * ans;for(int ch = 0; ch < 3; ++ch) {std::vector<std::pair<int, int>> init;for(int i = ss[ch]; i < n; i = nxt[i][ch])init.emplace_back(i, i);dfs(init, 1);}std::cout << ans << char(10);return 0;
}

D. Cut the Cake

队友开局写的签，我题意都没看

#include<bits/stdc++.h>
using namespace std;const int N = 205;string str[N];
int n, m, k;
int col[N], row[N], S[N][N];
vector<int> ansr, ansc;bool solve() {cin >> n >> m >> k;for (int i=1; i<=n; ++i) {cin >> str[i];str[i] = '$' + str[i];for (int j=1; j<=m; ++j) {int a = str[i][j]-'0';col[j] += a, row[i] += a;S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + a;}}for (int j=1; j<=m; ++j) col[j] += col[j-1]; for (int i=1; i<=n; ++i) row[i] += row[i-1];// printf("row:"); for (int i=1; i<=n; ++i) printf("%d ", row[i]); puts("");ansr.push_back(0); ansc.push_back(0);int lst = 0;for (int i=1; i<=n; ++i) {if (row[i] - row[lst] == k) {ansr.push_back(i);lst = i;}}lst = 0;for (int i=1; i<=m; ++i) {if (col[i] - col[lst] == k) {ansc.push_back(i);lst = i;}}// printf("r=%d c=%d\n", ansr.size(), ansc.size());if (ansr.size() != k+1 || ansc.size() != k+1) return false;// puts("11111");for (int i=1; i<=k; ++i) for (int j=1; j<=k; ++j) {int r=ansr[i], c=ansc[j], nr=ansr[i-1], nc=ansc[j-1];if (S[r][c]-S[nr][c]-S[r][nc]+S[nr][nc] != 1) return false;}return true;
}signed main() {ios::sync_with_stdio(0); cin.tie(0);bool ok = solve();if (!ok) cout << "NO\n";else {cout << "YES\n";for (int i=1; i<k; ++i) cout << ansr[i] << (i==k-1 ? '\n' : ' ');for (int i=1; i<k; ++i) cout << ansc[i] << (i==k-1 ? '\n' : ' ');}return 0;
}

F. Bad Word

首先如果串本身不是回文答案就是 \(1\)

可以证明，若串是 aaaaa,aabaa,ababa 等形式则一定无解，否则一定可以两次操作删空

#include<bits/stdc++.h>
using namespace std;int n;
string str;bool all_same(string str) {int len = str.length();for (int i=1; i<len; ++i) if (str[i] != str[0]) return false;return true;
}bool is_pan(string str) {int len = str.length();for (int i=0; i<len; ++i) if (str[i] != str[len-1-i]) return false;return true;
}bool is_ab(string str) {int len = str.length();if (len <= 2) return false;for (int i=2; i<len; ++i) if (str[i] != str[i%2]) return false;return true;
}int solve() {string str;cin >> n;cin >> str;if (!is_pan(str)) return 1;// cout << str << '\n';if (all_same(str)) return -1;if (n%2==0) return 2;if (is_ab(str)) return -1;if (all_same(str.substr(0, n/2)) && all_same(str.substr((n+1)/2, n/2))) return -1;return 2;    
}signed main() {ios::sync_with_stdio(0); cin.tie(0);cout << solve() << '\n';return 0;
}

G. Zenyk, Marichka and Interesting Game

首先根据经典的模仿策略，我们可以将每堆石子个数模 \(a+b\)，同时 \(a=b\) 的情况很好处理

此时每堆石子都满足一个人取了后另一个人不能取，直观上考虑会堆数奇偶性有关

不妨假设 \(a<b\)，此时发现如果存在一堆石子个数 \(x\) 满足 \(a\le x<b\) 或 \(2a\le x\)，则先手一定可以调整拿去次数的奇偶性从而必胜

对于 \(a>b\) 的情形，枚举先手拿哪一堆后就自动变为上述情况，简单判断即可

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int n,A,B,a[N];
int main()
{scanf("%d%d%d",&n,&A,&B);for (RI i=1;i<=n;++i)scanf("%d",&a[i]),a[i]%=(A+B);if (A==B){int cnt=0;for (RI i=1;i<=n;++i)cnt+=a[i]/A;puts(cnt%2==1?"Zenyk":"Marichka");return 0;}int x=min(A,B),y=max(A,B),num[3]={0,0,0};for (RI i=1;i<=n;++i){if (x<=a[i]&&a[i]<y) ++num[0];if (a[i]>=2*x) ++num[1];if (a[i]>=x) ++num[2];}if (A<B){if (num[0]||num[1]) puts("Zenyk");else puts(num[2]%2==1?"Zenyk":"Marichka");return 0;}for (RI i=1;i<=n;++i){if (a[i]<A) continue;if (x<=a[i]&&a[i]<y) --num[0];if (a[i]>=2*x) --num[1];if (a[i]>=x) --num[2];a[i]-=A;if (x<=a[i]&&a[i]<y) ++num[0];if (a[i]>=2*x) ++num[1];if (a[i]>=x) ++num[2];if (num[0]==0&&num[1]==0&&num[2]%2==0){puts("Zenyk"); return 0;}if (x<=a[i]&&a[i]<y) --num[0];if (a[i]>=2*x) --num[1];if (a[i]>=x) --num[2];a[i]+=A;if (x<=a[i]&&a[i]<y) ++num[0];if (a[i]>=2*x) ++num[1];if (a[i]>=x) ++num[2];}return puts("Marichka"),0;
}

H. Frog Jumping

首先检查相邻石子间是否有间距大于 \(D\) 的，若有则让 \(c_i\) 最小的青蛙把石子全跳了，剩下的青蛙直接 \(1\to n\) 大跳

否则考虑二分有 \(s\) 只青蛙可以不进行大跳，检验的话就是把石子隔 \(s\) 个分个某个青蛙然后检查一遍距离即可

注意特判 \(1\to n\) 可以不消耗代价的情况

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<assert.h>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int n,m,k,d,c[N],a[N];
int main()
{scanf("%d%d%d%d",&n,&m,&k,&d);for (RI i=1;i<=m;++i) scanf("%d",&c[i]);sort(c+1,c+m+1);for (RI i=1;i<=k;++i) scanf("%d",&a[i]);sort(a+1,a+k+1); a[0]=1; a[k+1]=n;if (n-1<=d) return puts("0"),0;bool flag=0;for (RI i=0;i+1<=k+1;++i)if (a[i+1]-a[i]>d) { flag=1; break; }long long ans=0;if (flag){for (RI i=0;i+1<=k+1;++i)if (a[i+1]-a[i]>d) ans+=c[1];for (RI i=2;i<=m;++i) ans+=c[i];return printf("%lld",ans),0;}int l=1,r=min(k,m),res=0;while (l<=r){int mid=l+r>>1;auto check=[&](CI s){for (RI i=1;i<=k;++i){int pre=max(0,i-s);if (a[i]-a[pre]>d) return 0;int nxt=min(k+1,i+s);if (a[nxt]-a[i]>d) return 0;}return 1;};if (check(mid)) res=mid,l=mid+1; else r=mid-1;}assert(res!=0);for (RI i=1;i<=m-res;++i) ans+=c[i];return printf("%lld",ans),0;
}

I. Slot Machine

首先不难发现最优策略只会选择至多两种箱子进行取球

选一种箱子的情况根据鸽笼原理，求出其颜色数 \(col\) 后，若该箱子存在个数大于 \(1\) 的球，则用 \(col+1\) 更新答案

选两种箱子的话考虑对第一次取的箱子中每种颜色赋一个权值，表示抽出这种颜色后去其它箱子抽该颜色需要的最小次数

不难发现这个权值就是除了这个箱子外，有该颜色出现的箱子中的颜色数量（这里还是要用鸽笼原理分析一波）

求出权值后考虑最坏情况，即权值大的球总是被先抽出来，把权值降序排序更新答案即可

#include<cstdio>
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005,INF=1e9;
int n,mn[N],smn[N],col[N]; map <int,int> box[N];
int main()
{int ans=INF;for (RI i=1;i<=100000;++i)mn[i]=smn[i]=INF;scanf("%d",&n);for (RI i=1;i<=n;++i){int L; scanf("%d",&L);for (RI j=1;j<=L;++j){int x; scanf("%d",&x);box[i][x]+=1;}col[i]=(int)box[i].size();for (auto [c,num]:box[i]){if (num>=2) ans=min(ans,col[i]+1);if (col[i]<mn[c]) smn[c]=mn[c],mn[c]=col[i];else if (col[i]<smn[c]) smn[c]=col[i];}}for (RI i=1;i<=n;++i){vector <int> val;for (auto [c,num]:box[i]){int tmp=(mn[c]!=col[i]?mn[c]:smn[c]);val.push_back(tmp);}sort(val.begin(),val.end(),greater <int>());// printf("box %d: ",i);// for (auto x:val) printf("%d ",x); putchar('\n');for (RI i=0;i<(int)val.size();++i)ans=min(ans,val[i]+i+1);}return printf("%d",ans),0;
}

J. Half is Good

7 年后的评测机直接暴力秒了此题，如何呢

#include<bits/stdc++.h>
using namespace std;
#define uint unsigned long longconst int N = 1e7+5;
int n, m;
struct Edge{uint w; int u, v;
}e[N];int id[N],fa[N];
unsigned s;
int gf(int x) {return x==fa[x] ? x : fa[x]=gf(fa[x]);}
bitset <N> ans;uint getNext() {s = (s ^ (s << 13));s = (s ^ (s >> 17));s = (s ^ (s << 5));return s;
}signed main() {ios::sync_with_stdio(0); cin.tie(0);cin >> n >> m >> s;for (int i = 0; i < m; ++i) {e[i].u = getNext() % n;e[i].v = getNext() % n;e[i].w = getNext() / 4;e[i].w = e[i].w * getNext(); // watch out for integer overflowid[i] = i;// there is an undirected edge between u and v with weight w// cout << e[i].u << ' ' << e[i].v << ' ' << e[i].w << '\n';}auto cmp = [&] (const int& x,const int& y) {return e[x].w < e[y].w;};sort(id, id+m, cmp);int cnt = 0;for (int i=0; i<n; ++i) fa[i] = i;for (int i=0; i<m; ++i) {int idx = id[i];if (gf(e[idx].u) != gf(e[idx].v)) {fa[gf(e[idx].u)] = gf(e[idx].v);++cnt;ans[idx] = true;if (2*cnt>=n-1) break;}}uint res = 0;for (int i=0; i<m; ++i) {int j = i/32;if (j != (i-1)/32) {cout << res << ' ';res = 0;}if (ans[i]) res += (1LL << (i%32));}cout << res << '\n';return 0;
}

L. Impress Her

直接暴力，根据经典结论枚举每种数对应的矩形内部的所有点复杂度是 \(O(n^3)\) 的，打个时间戳即可快速统计

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=505,M=1e6+5,INF=1e9;
int n,m,a[N][N],vis[M],xl[M],xr[M],yl[M],yr[M];
int main()
{scanf("%d%d",&n,&m);for (RI i=1;i<=1000000;++i)xl[i]=yl[i]=INF,xr[i]=yr[i]=-INF;for (RI i=1;i<=n;++i)for (RI j=1;j<=m;++j){int s; scanf("%d",&s); a[i][j]=s;xl[s]=min(xl[s],i); xr[s]=max(xr[s],i);yl[s]=min(yl[s],j); yr[s]=max(yr[s],j);}int ans=0;for (RI i=1;i<=1000000;++i){if (xl[i]==INF) continue;for (RI x=xl[i];x<=xr[i];++x)for (RI y=yl[i];y<=yr[i];++y){int j=a[x][y];if (j==i) continue;if (vis[j]==i) continue;if (xl[i]<=xl[j]&&xr[j]<=xr[i]&&yl[i]<=yl[j]&&yr[j]<=yr[i]){vis[j]=i; ++ans;}}}return printf("%d",ans),0;
}

Postscript

比赛临近还是一点不训啊，不会真要成旅游队了吧

资讯详情

Moscow International Workshops 2017. Day 4. Lviv NU Contest, GP of Ukraine