Preface
纯纯的智商场，只能说老外的出题风格和国内的比赛差异还是挺大的
这场开局被签到题H反杀后灰溜溜地下机，结果后面的题出的都还挺顺的
等到最后徐神把J过掉后我们都以为D是个大分类讨论（实际上机房里的学长们都是用分类讨论过的），就不想写了挂机到结束
后面看题解发现确实是分类讨论，但民间做法有一个更加好写的贪心做法，而且简单到让人怀疑人生，我直接呃呃
A. Walking Boy
签到
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=105;
int t,n,a[N];
int main()
{
//freopen("A.in","r",stdin); freopen("A.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
int c=(a[1]/120)+((1440-a[n])/120);
for (i=2;i<=n;++i) c+=(a[i]-a[i-1])/120;
puts(c>=2?"YES":"NO");
}
return 0;
}
B. Vittorio Plays with LEGO Bricks
貌似是个细节很多的区间DP的说，看着徐神从开场写到150min的时候才过
主要好像是要根据奇偶性进行讨论，因此会比较复杂，但由于不是我写的就不多赘述
#include <bits/stdc++.h>
using llsi = long long signed int;
int n, h, x[301];
struct pt { int x, y; };
std::vector<pt> fx(pt a, pt b) {
if(a.x > b.x) std::swap(a, b);
// int res = 0;
if(a.y > b.y) a.x += a.y - b.y, a.y = b.y;
else b.x -= b.y - a.y, b.y = a.y;
int cc = (b.x - a.x + 1) >> 1;
a.y -= cc, b.y -= cc;
a.x += cc, b.x -= cc;
if(a.y < 0) return { {-1, 0} };
if(a.x == b.x) return { a };
return { a, b };
}
llsi dis(pt a, pt b) {
if(a.y < b.y) std::swap(a, b);
if(b.y == 0) return a.y;
if(std::abs(a.x - b.x) > a.y - b.y) return 2e18;
return std::abs(a.y - b.y);
}
llsi dp[301][301][2];
pt dcrs[301][301][2];
void updmn(llsi &a, const llsi &b) {
if(b < a) a = b;
}
int main() {
// freopen("3.in", "r", stdin);
std::ios::sync_with_stdio(false);
// for(auto [x, y]: fx({3, 5}, {5, 4})) std::cout << x << ' ' << y << char(10);
// return 0;
std::cin >> n >> h;
for(int i = 1; i <= n; ++i) std::cin >> x[i];
memset(dp, 0x1f, sizeof dp);
for(int i = 1; i <= n; ++i) dp[i][i][0] = 0, dcrs[i][i][0] = {x[i], h};
for(int l = 2; l <= n; ++l) for(int i = 1; i + l - 1 <= n; ++i) {
int j = i + l - 1;
auto crs = fx({x[i], h}, {x[j], h});
for(size_t k = 0; k < crs.size(); ++k) dcrs[i][j][k] = crs[k];
for(int k = i; k < j; ++k) {
for(size_t wl = 0; wl < 2; ++wl) if(dp[i ][k][wl] < 1e15)
for(size_t wr = 0; wr < 2; ++wr) if(dp[k + 1][j][wr] < 1e15)
for(size_t wm = 0; wm < crs.size(); ++wm)
updmn(dp[i][j][wm],
dp[i ][k][wl] + dis(dcrs[i ][k][wl], crs[wm]) +
dp[k + 1][j][wr] + dis(dcrs[k + 1][j][wr], crs[wm]) -
(crs[0].x >= 0));
}
// for(size_t k = 0; k < crs.size(); ++k) std::cout << '[' << i << ", " << j << ", " << k << "] = " << dp[i][j][k]
// << " (" << crs[k].x << " ," << crs[k].y << ")\n";
}
auto &[l, r] = dp[1][n];
auto &[lp, rp] = dcrs[1][n];
l += dis(lp, {0, 0}), r += dis(rp, {0, 0});
std::cout << std::min(l, r) << std::endl;
return 0;
}
C. Library game
很有意思的一个题，本来思路卡了但刚好听到银牌爷他们队喊了一个很关键的点就会了，什么窃听风云.jpg
首先可以将\(x_i\)从大到小排序，不难发现先手一定是从大到小取这些区间，考虑什么时候后手存在最优策略
根据手玩很容易发现，若存在\(i\in[1,n]\)使得\(x_i\times i>m\)，则我们可以用如下方法来构造一组后手获胜的方案
对于所有的\(j\in[1,m]\and x_i|j\)的位置，我们将其标记为关键点，不难发现关键点的数目为\(i-1\)
由于有\(i\)个区间的长度都\(\ge x_i\)，那么这些区间一定会至少覆盖到一个关键点，而根据抽屉原理此时一定有某个关键点被覆盖两次，则后手必胜
否则如果不存在这样的下标就选择先手即可，策略的话就是每次在剩下的区间里找一个长度\(\ge x_i\)且最小的区间即可
#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=5005;
int n,m,x[N],y,a; bool vis[N];
int main()
{
//freopen("C.in","r",stdin); freopen("C.out","w",stdout);
RI i,j,k; for (scanf("%d%d",&n,&m),i=1;i<=n;++i) scanf("%d",&x[i]);
sort(x+1,x+n+1,greater <int>()); int pos=-1;
for (i=1;i<=n;++i) if (i*x[i]>m) { pos=i; break; }
if (~pos)
{
printf("Bernardo\n"); fflush(stdout);
for (i=1;i<=n;++i)
{
scanf("%d%d",&y,&a); bool flag=0;
for (j=a;j<=a+y-1;++j) if (j%x[pos]==0)
{
printf("%d\n",j); fflush(stdout); flag=1; break;
}
if (!flag) printf("%d\n",a),fflush(stdout);
}
} else
{
printf("Alessia\n"); fflush(stdout);
for (i=1;i<=n;++i)
{
int pos,mi=1e9;
for (j=1;j<=m;)
{
if (vis[j]) { ++j; continue; }
for (k=j;k<=m&&!vis[k];++k);
if (k-j>=x[i]&&k-j<mi) pos=j,mi=k-j; j=k;
}
printf("%d %d\n",x[i],pos); fflush(stdout);
scanf("%d",&y); vis[y]=1;
}
}
return 0;
}
D. Teamwork
比赛的时候祁神讨论了很多种情况，然后我们都认为是个分类讨论题遂最后弃疗了，后面看到一种贪心的做法才恍然大悟
考虑按照如下的贪心策略考虑，先优先保证每个时刻都有人在写题
然后我们发现如果某个时刻我们可以选择做难题的话，那么把难题换成简单题或者中等题也是可以的，所以我们优先做难度大的题
同时选谁来做也是个问题，我们发现如果找一个完成上道题的时间和当前时刻最接近的人来做都可以完成这道题的话，话别人来肯定也是可以的，因此我们优先找间隔时间最小的人
然后按照这个策略来做即可，复杂度\(O(l\times 3\times 3)\)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<array>
#define RI register int
#define CI const int&
using namespace std;
struct ifo
{
int id,tim;
friend inline bool operator < (const ifo& A,const ifo& B)
{
return A.tim>B.tim;
}
}o[3];
int l,c[5]; vector <array <int,3>> ans;
int main()
{
//freopen("D.in","r",stdin); freopen("D.out","w",stdout);
RI i,j,k; scanf("%d%d%d%d",&c[2],&c[3],&c[4],&l);
o[0].id=1; o[1].id=2; o[2].id=3;
for (i=1;i<=l;++i)
{
for (sort(o,o+3),j=4;j>=2;--j)
{
if (!c[j]) continue; bool flag=0;
for (k=0;k<3&&!flag;++k) if (i-o[k].tim>=j)
ans.push_back({o[k].id,i-j,i}),o[k].tim=i,--c[j],flag=1;
if (flag) break;
}
}
printf("%d\n",ans.size());
for (auto [id,l,r]:ans) printf("%d %d %d\n",id,l,r);
return 0;
}
E. Crossing the Railways
防AK题，弃疗
F. Train Splitting
很有意思的图论构造题，感觉这题还挺有意思的但不知道为什么就被过穿了
首先不妨先求一个生成树出来，然后将其上的所有边都赋成颜色\(1\)，然后考虑将剩下的边都赋成颜色\(2\)
但这里求生成树的时候有一个技巧，我们不希望剩下的颜色为\(2\)的边仍然可以构成生成树，因此不妨优先把某个点（钦定为\(1\)号点）的所有出边都加入生成树\(1\)中，这样剩下的边一定无法连接到\(1\)号点
然后由于还要满足\(1\)不连通整个图的限制，我们不妨枚举生成树\(1\)中的每条边，进行讨论：
- 若修改这条边的颜色为\(2\)是否会构成\(2\)颜色的生成树，如果不会将其改为\(2\)就是答案
- 否则将这条边的颜色改为\(3\)即可得到一组合法解，因为此时\((1,2),(2,3),(1,3)\)所有组合都可以连通整个边，而单独某个颜色就不能
总复杂度\(O(n+m)\)，估计是由于checker的复杂度所以才出的现在的数据范围
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=55;
int t,n,m,x[N*N],y[N*N],col[N*N];
struct DSU
{
int fa[N];
inline void init(CI n)
{
for (RI i=1;i<=n;++i) fa[i]=i;
}
inline int getfa(CI x)
{
return fa[x]!=x?fa[x]=getfa(fa[x]):x;
}
inline void merge(CI x,CI y)
{
fa[getfa(x)]=getfa(y);
}
inline bool query(CI x,CI y)
{
return getfa(x)==getfa(y);
}
}S1,S2;
int main()
{
//freopen("F.in","r",stdin); freopen("F.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i,j; for (scanf("%d%d",&n,&m),i=1;i<=m;++i)
if (scanf("%d%d",&x[i],&y[i]),col[i]=0,x[i]>y[i]) swap(x[i],y[i]);
for (S1.init(n),i=1;i<=m;++i) if (x[i]==1) S1.merge(x[i],y[i]),col[i]=1;
for (i=1;i<=m;++i) if (!col[i]&&!S1.query(x[i],y[i])) col[i]=1,S1.merge(x[i],y[i]);
for (i=1;i<=m;++i) if (!col[i]) col[i]=2; int ans;
for (S2.init(n),i=1;i<=m;++i) if (col[i]==1)
{
S2.merge(x[i],y[i]); bool flag=1;
for (j=1;j<=m;++j) if (col[j]==2) S2.merge(x[j],y[j]);
for (j=2;j<=n;++j) if (!S2.query(1,j)) flag=0;
if (flag) ans=col[i]=3; else ans=col[i]=2; break;
}
for (printf("%d\n",ans),i=1;i<=m;++i) printf("%d%c",col[i]," \n"[i==m]);
}
return 0;
}
G. Another Wine Tasting Event
诈骗题，但仔细一看题目中的0.5ms好像就在暗示着这就是个\(O(n)\)的结论题
这题的结论其实很简单，对于所有的长度恰为\(n\)的区间，统计它们的W的个数，最后输出个数最多的那个区间对应的数即可
证明的话考虑设最后找到的区间为\([L,R]\)，则对于任意\(l<L\)，总能找到一个右端点\(r\)使得\([l,r]\)中W的个数与\([L,R]\)中的相等，在右边也同理，因此这样至少有\(n\)个区间符合要求
复杂度\(O(n)\)
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=2e6+5;
int n,pfx[N]; char s[N];
int main()
{
//freopen("G.in","r",stdin); freopen("G.out","w",stdout);
RI i; for (scanf("%d%s",&n,s+1),i=1;i<=2*n-1;++i) pfx[i]=pfx[i-1]+(s[i]=='W');
int ans=pfx[n]; for (i=n+1;i<=2*n-1;++i) ans=max(ans,pfx[i]-pfx[i-n]);
return printf("%d",ans),0;
}
H. Beppa and SwerChat
签到失败，耻辱下机，祁神出手，直接顿悟
首先不妨把第一个排列对应的数映射成\(1,2,3\cdots\)，然后再映射到第二个排列上
不难发现此时\(b_n\)对应的人一定可以被钦定为没有上线，考虑剩下不上线人数的最大值
手玩一下会发现其实就是从末尾向前的连续递减段的人可以不上线，直接扫一遍即可
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int t,n,a[N],b[N],f[N],pos[N];
int main()
{
//freopen("H.in","r",stdin); freopen("H.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]),pos[a[i]]=i;
for (i=1;i<=n;++i) scanf("%d",&b[i]),b[i]=pos[b[i]];
for (i=n;i>1;--i) if (b[i-1]>b[i]) break;
printf("%d\n",i-1);
}
return 0;
}
I. Spinach Pizza
几何博弈论，但是祁神很早之前做过，直接省下大量时间
结论就是偶数个点选先手，奇数个点选后手，然后每次操作选一个面积最小的角切下来即可，证明的话看Tutorial
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct Pt{
int x, y, id;
int crs(Pt b)const{return x*b.y-y*b.x;}
Pt operator-(Pt b)const{return Pt{x-b.x, y-b.y};}
};
vector<Pt> vec;
void del(int x){
for (auto it=vec.begin(); it!=vec.end(); ++it){
if (it->id==x){
vec.erase(it);
break;
}
}
}
void out(){
int sz=vec.size();
int area=(vec[1]-vec[0]).crs(vec[sz-1]-vec[0]);
int id=vec[0].id;
for (int i=1; i<sz; ++i){
int tmp = (vec[(i+1)%sz]-vec[i]).crs(vec[i-1]-vec[i]);
if (tmp < area){
area = tmp;
id = vec[i].id;
}
}
cout << id << endl;
del(id);
int x; cin >> x;
del(x);
}
int n;
signed main(){
cin >> n;
vec.resize(n);
for (int i=0; i<n; ++i){
cin >> vec[i].x >> vec[i].y;
vec[i].id = i+1;
}
if (n%2){
cout << "Beatrice" << endl;
int x; cin >> x;
del(x);
--n;
}else cout << "Alberto" << endl;
while (n>3){
out();
n-=2;
}
return 0;
}
J. Italian Data Centers
ORZ徐神，轻松解决了高维立方体中的最短路，不愧是高维生物
注意到我们可以把每个数看作一个\(k\)长度的\(01\)串，同时会发现同色边连接的点不会影响每一位的取值，而异色边连接的点的状态相当于是按位取反
把每个点拆成正反两个点，跑Floyd求出两点间的最短距离，然后枚举两个点对，讨论中间不同的位的影响即可
复杂度\(O(n^3+n^2\times k)\)
#include <bits/stdc++.h>
using llsi = long long signed int;
constexpr int $n = 101 << 1;
int n, m, k, c[$n];
llsi dp[$n][$n];
int main() {
// freopen("4.in", "r", stdin);
std::ios::sync_with_stdio(false);
std::cin >> n >> m >> k;
for(int i = 1; i <= n; ++i) std::cin >> c[i];
memset(dp, 0x1f, sizeof dp);
for(int i = 1; i <= 2 * n; ++i) dp[i][i] = 0;
for(int i = 1; i <= n; ++i) dp[i][i + n] = dp[i + n][i] = k;
for(int i = 1, a, b; i <= m; ++i) {
std::cin >> a >> b;
if(c[a] == c[b])
dp[a ][b ] = dp[b ][a ] = 1,
dp[a + n][b + n] = dp[b + n][a + n] = 1;
else
dp[a ][b + n] = dp[b + n][a ] = 1,
dp[a + n][b ] = dp[b ][a + n] = 1;
}
int dn = n << 1;
for(int k = 1; k <= dn; ++k)
for(int i = 1; i <= dn; ++i)
for(int j = 1; j <= dn; ++j)
dp[i][j] = std::min(dp[i][j], dp[i][k] + dp[k][j]);
llsi ans = 0;
// for(int i = 1; i <= dn; ++i) for(int j = 1; j <= dn; ++j)
// std::cerr << dp[i][j] << char(j == dn ? 10 : 32);
for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) {
for(int diff = 0; diff <= k; ++diff) {
ans = std::max( ans, std::min({
dp[i][j] + diff,
dp[i][j + n] + (k - diff),
dp[i + n][j] + (k - diff),
dp[i + n][j + n] + diff
}));
}
}
std::cout << ans << std::endl;
return 0;
}
K. Uniform Chemistry
概率题再加上\(10^{18}\)，一眼不会做
L. Controllers
挺签的一个题，徐神开场写的，我题目都没看
#include <bits/stdc++.h>
using llsi = long long signed int;
inline llsi gcd(llsi a, llsi b) {
return b ? gcd(b, a % b) : a;
}
int n, q;
llsi a, b, cp = 0, cm = 0;
std::string s;
int main() {
// freopen("3.in", "r", stdin);
std::ios::sync_with_stdio(false);
std::cin >> n >> s;
for(char &c: s) if(c == '+') cp += 1; else cm += 1;
if(cp < cm) std::swap(cp, cm);
std::cin >> q;
while(q--) {
std::cin >> a >> b;
if(cp == cm) {
std::cout << "YES\n";
continue;
}
if(a == b) {
std::cout << "NO\n";
continue;
}
if(a > b) std::swap(a, b);
const llsi gab = gcd(a, b), lab = a / gab * b;
const llsi ca = lab / a, cb = lab / b, cd = (ca - cb);
if((cp - cm) % cd) {
std::cout << "NO\n";
continue;
}
const llsi cc = (cp - cm) / cd;
if(cp < cc * ca || cm < cc * cb) {
std::cout << "NO\n";
continue;
}
std::cout << "YES\n";
}
return 0;
}
M. Parmigiana With Seafood
很好奇这种人类智慧题是怎么出出来的，感觉看题解能勉强看懂，但完全不知道是怎么想到的
这题搞到最后就是个结论题，我们定义两个点\((x,y)\)为bad pair当且仅当它们之间的距离为奇数
定义三个点\((x,y,z)\)为bad triple当且仅当存在\(m\)使得在断开\(m\)后\(x,y,z\)不连通，并且\(m\)到\(x,y,z\)的距离均为偶数
然后最后得到以下结论：
- 当\(n\)为偶数时，答案就是\(n\)
- 当\(n\)为奇数时，答案就是满足以下限制的点中编号最大的那个：
- 初始时就是叶子节点
- 某个点\(x\)满足\((x,n)\)是bad pair
- \(\min(x,y)\)对于任意的bad triple\((x,y,n)\)
- \(\min(x,y,z)\)对于任意的bad triple\((x,y,z)\)，且它们对应断开的点\(m\)为\(n\)
以上结论的得出以及证明可以看Tutorial，里面写的已经十分详尽了
最后实现的话就以\(n\)为根DFS一遍即可，分别讨论清楚上述条件即可
#include<cstdio>
#include<iostream>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int n,x,y,dep[N],f[N][2],ans,ret,mx[3]; vector <int> v[N];
inline void DFS(CI now,CI fa)
{
dep[now]=dep[fa]+1; f[now][0]=(v[now].size()>1?now:0);
for (auto to:v[now]) if (to!=fa)
DFS(to,now),f[now][0]=max(f[now][0],f[to][1]),f[now][1]=max(f[now][1],f[to][0]);
if (dep[now]%2==1) ans=max(ans,now); else
{
ret=max(ret,now); int mx[2]={0,0};
for (auto to:v[now]) if (to!=fa)
{
if (f[to][1]>mx[0]) mx[1]=mx[0],mx[0]=f[to][1];
else if (f[to][1]>mx[1]) mx[1]=f[to][1];
}
ans=max(ans,mx[1]);
}
}
int main()
{
//freopen("M.in","r",stdin); freopen("M.out","w",stdout);
RI i; for (scanf("%d",&n),i=1;i<n;++i)
scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
if (n%2==0) return printf("%d\n",n),0;
for (i=1;i<=n;++i) if (v[i].size()==1) ans=max(ans,i);
for (auto to:v[n])
{
ret=0; DFS(to,n);
if (ret>mx[0]) mx[2]=mx[1],mx[1]=mx[0],mx[0]=ret;
else if (ret>mx[1]) mx[2]=mx[1],mx[1]=ret;
else if (ret>mx[2]) mx[2]=ret;
}
return printf("%d",max(ans,mx[2])),0;
}
N. Count Permutations
好劲的计数题，话说杨表是什么，能吃吗？
Postscript
思维题我也写不来，套路题也写不来，这下可怎么办啊苦露西