Preface
战术最失败的一集，徐神从开场就被模拟题关住了，直到 4h30min 的时候才放出来
然后剩下的题也开的不顺，最后感觉好多题都没写就 7 题下班了
这场也是延续了之前几场的一贯画风，最后 1h 我在狂暴鸿儒一个题，然后挂飞了也没过，赛后稍微一想就发现又犯了个唐氏错误
A. Bingo
沟槽的大模拟
首先对于倍数的情况写一个高精模低精和高精加高精即可，考虑子串的情况如何处理
手玩下会发现最后子串出现的位置不会偏移末尾太多，大约是 \(m\) 的长度级别，然后模拟下这一部分即可
实现的时候要注意各种神秘细节
#include <bits/stdc++.h>
struct bignum {
int a[1000005], w;
bignum& assign(const int rhs) {
w = 0;
return (*this) += rhs;
}
bignum& assign(const std::string &s) {
if(s == "0") { w = 0; return *this; }
w = s.size();
for(int i = 0; i < w; ++i) a[i] = s[w - 1 - i] - '0';
return *this;
}
bignum& operator +=(const int rhs) {
a[w] = 0, a[0] += rhs;
// std::cout << "a[0] = " << a[0] << char(10);
for(int i = 0; i < w; ++i) {
a[i + 1] += a[i] / 10;
a[i] %= 10;
}
for(int i = w; a[i]; ++i) {
a[i + 1] = a[i] / 10;
a[i] %= 10;
w++;
}
return *this;
}
int operator %(const int m) const {
int64_t res = 0;
for(int i = w - 1; i >= 0; --i) res = (res * 10 + a[i]) % m;
return res;
}
};
std::ostream& operator << (std::ostream& out, const bignum &n) {
if(n.w == 0) out << '0';
else for(int i = n.w - 1; i >= 0; --i) out << char(n.a[i] + '0');
return out;
}
template<typename I>
int64_t to_int(I __first, I __last) {
int64_t res = 0;
while(__first < __last) res = res * 10 + (*__first++ - '0');
return res;
}
void work() {
std::string sn, sm;
std::cin >> sn >> sm;
static bignum n;
n.assign(sn);
int64_t m = to_int(sm.begin(), sm.end());
n += 1;
int64_t ans = n % m;
if(ans == 0) {
std::cout << n << char(10);
return ;
}
ans = m - ans;
int64_t hkr = 0, b10 = 1;
for(int i = 0; i <= n.w - int64_t(sm.size()); ++i) {
int64_t part = 0;
for(int j = sm.size() - 1; j >= 0; --j)
part = part * 10 + n.a[i + j];
// std::cerr << "part = " << part << char(10);
if(part == m) { ans = 0; break; }
if(part < m && i <= 15) {
__int128_t upd = m - part;
for(int k = 0; k < i; ++k) upd *= 10;
for(int k = 0, b10 = 1; k < i; ++k, b10 *= 10)
upd -= b10 * n.a[k];
ans = std::min(__int128_t(ans), upd);
}
if(i > 0 && part == m - 1) /*std::cerr << "FUCK " << hkr << "\n", */ans = std::min(int64_t(ans), hkr);
if(i == 0) hkr = 10 - n.a[i];
else {
hkr += b10 * (9 - n.a[i]);
if(hkr > ans) hkr = ans;
}
b10 *= 10;
if(b10 > ans) b10 = ans;
}
n += ans;
std::cout << n << char(10);
return ;
}
int main() {
std::ios::sync_with_stdio(false);
int T; std::cin >> T; while(T--) work();
return 0;
}
B. Simulated Universe
直到比赛结束我才知道这个题的题意，后面发现是个很丁真的 DP 题
考虑设 \(f_{i,j}\) 表示处理了前 \(i\) 个位置，且留有 \(j\) 次向后的升级时，最多能升级的次数
转移按照定义十分显然，复杂度 \(O(n^2)\)
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=8005,INF=1e9;
int t,n,f[N][N],a,b; char ch[10];
int main()
{
for (scanf("%d",&t);t;--t)
{
scanf("%d",&n);
for (RI i=0;i<=n;++i) for (RI j=0;j<=n+1;++j) f[i][j]=-INF;
f[0][0]=0; int pre=0;
for (RI i=1;i<=n;++i)
{
scanf("%s",ch);
if (ch[0]=='B')
{
++pre;
for (RI j=0;j<=n;++j)
f[i][j]=max(f[i][j],max(f[i-1][j],f[i-1][j+1]+1));
} else
{
scanf("%d%d",&a,&b);
for (RI j=0;j<=n;++j)
{
f[i][j]=max(f[i][j],min(pre,f[i-1][j]+a));
f[i][j]=max(f[i][j],f[i-1][max(0,j-b)]);
}
}
}
int ans=0; for (RI i=0;i<=n;++i) ans=max(ans,f[n][i]);
printf("%d\n",pre+ans);
}
return 0;
}
C. Challenge NPC
神秘构造题，想到二分图就很简单了
构造一个左右各 \(k+2\) 个点的二分图，每部分的点向另一侧编号严格小于它的点连边
此时按照题目中的贪心法得到的颜色数为 \(k+2\)，二分图的实际染色数为 \(2\)，符合题意
#include<cstdio>
#include<iostream>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
const int N=1024;
int k,col[N],L[N],R[N]; vector <pair <int,int>> E;
int main()
{
scanf("%d",&k);
for (RI i=2;i<=k+2;++i) for (RI j=1;j<i;++j)
E.push_back({2*i-1,2*j}),E.push_back({2*i,2*j-1});
printf("%d %d %d\n",(k+2)*2,(int)E.size(),2);
for (RI i=1;i<=k+2;++i) printf("%d %d ",1,2); putchar('\n');
for (auto [x,y]:E) printf("%d %d\n",x,y);
return 0;
}
D. Puzzle: Easy as Scrabble
神秘搜索题
考虑把限制看作推箱子，往一个固定方向一直走直到遇到一个不是 x 的位置为止，然后将这个限制暂存
如果某个位置上有多种类型的箱子，则该位置只能是 x，同时将该位置放进一个队列中，每次取出队首并将上面暂存的限制继续推动即可
由于每个位置只会被变成 x 一次，且变成 x 后至多只有四个方向的箱子会经过它，因此复杂度是 \(O(nm)\) 的
#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#define RI register int
#define CI const int&
using namespace std;
const int N=1005,dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
int n,m; char s[N][N]; vector <pair <int,int>> res[N][N];
queue <pair <int,int>> Q;
inline bool GO(int x,int y,CI d,CI c)
{
if (c=='.') return 1;
for (;;x+=dx[d],y+=dy[d])
{
if (x<1||x>n||y<1||y>m) return 0;
if (s[x][y]!='x')
{
res[x][y].push_back({d,c});
if (s[x][y]=='.') s[x][y]=c;
else if (s[x][y]!=c)
s[x][y]='x',Q.push({x,y});
return 1;
}
}
return 0;
}
int main()
{
//freopen("D.in","r",stdin);
scanf("%d%d",&n,&m);
for (RI i=0;i<=n+1;++i) scanf("%s",s[i]);
for (RI j=1;j<=m;++j)
{
if (!GO(1,j,1,s[0][j])) return puts("NO"),0;
if (!GO(n,j,3,s[n+1][j])) return puts("NO"),0;
}
for (RI i=1;i<=n;++i)
{
if (!GO(i,1,0,s[i][0])) return puts("NO"),0;
if (!GO(i,m,2,s[i][m+1])) return puts("NO"),0;
}
while (!Q.empty())
{
auto [x,y]=Q.front(); Q.pop();
for (auto [d,c]:res[x][y])
if (!GO(x,y,d,c)) return puts("NO"),0;
}
puts("YES");
for (RI i=1;i<=n;++i,putchar('\n'))
for (RI j=1;j<=m;++j)
{
if (s[i][j]=='x') s[i][j]='.';
putchar(s[i][j]);
}
return 0;
}
E. Team Arrangement
\(n\le 60\) 就提示我们暴力求出分拆数，打表发现 \(60\) 的分法大概是 \(10^6\) 级别，可以接受
考虑验证一组拆分是否合法，naive 的想法就是直接跑匹配，然后赛时写了匈牙利和 Dinic 都没冲过去
后面意识到要用性质，考虑从小到大枚举每个队伍的大小 \(k\)，对于所有 \(l_i\le k\) 且未被匹配的人，选择 \(r_i\) 最小的 \(k\) 个与之匹配即可
用优先队列实现可以卡过，看题解好像有用位运算做到去 $\log $ 的做法，感觉十分神秘
#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#define RI register int
#define CI const int&
using namespace std;
const int N=65,INF=1e9;
int n,cnt,l[N],r[N],w[N],ans=-INF; vector <int> vec,rpos[N];
inline int calc(vector <int>& vec)
{
++cnt;
//for (auto x:vec) printf("%d ",x); putchar('\n');
int res=0; for (auto x:vec) res+=w[x];
if (res<ans) return -INF;
priority_queue <int,vector <int>,greater <int>> hp;
int k=1;
for (auto x:vec)
{
while (k<=x)
{
for (auto y:rpos[k]) hp.push(y);
++k;
}
while (!hp.empty()&&hp.top()<x) hp.pop();
if ((int)hp.size()<x) return -INF;
for (RI i=1;i<=x;++i) hp.pop();
}
return res;
}
inline void DFS(vector <int>& vec,CI sum,CI lst)
{
if (sum==n) return (void)(ans=max(ans,calc(vec)));
for (RI i=lst;i<=n-sum;++i) vec.push_back(i),DFS(vec,sum+i,i),vec.pop_back();
}
int main()
{
scanf("%d",&n);
for (RI i=1;i<=n;++i) scanf("%d%d",&l[i],&r[i]),rpos[l[i]].push_back(r[i]);
for (RI i=1;i<=n;++i) scanf("%d",&w[i]);
DFS(vec,0,1);
//printf("count = %d\n",cnt);
if (ans==-INF) puts("impossible"); else printf("%d",ans);
return 0;
}
F. Stage: Agausscrab
签到模拟题
#include<cstdio>
#include<iostream>
#include<string>
#include<algorithm>
#define RI register int
#define CI const int&
#define fi first
#define se second
using namespace std;
const int N=1005;
int n; pair <string,pair <int,int>> p[N];
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
cin>>n;
for (RI i=1;i<=n;++i) cin>>p[i].fi>>p[i].se.fi,p[i].se.se=i;
auto cmp_rk=[&](const pair <string,pair <int,int>>& A,pair <string,pair <int,int>>& B)
{
return A.se.fi>B.se.fi;
};
sort(p+1,p+n+1,cmp_rk); int rk=1;
for (RI i=1;i<=n;++i)
{
while (rk<i&&p[rk].se.fi>p[i].se.fi) ++rk;
int tmp=min((int)p[i].fi.size(),rk);
for (RI j=1;j<=tmp;++j) p[i].fi.pop_back();
}
auto cmp_id=[&](const pair <string,pair <int,int>>& A,pair <string,pair <int,int>>& B)
{
return A.se.se<B.se.se;
};
sort(p+1,p+n+1,cmp_id);
string ans="";
for (RI i=1;i<=n;++i) ans+=p[i].fi;
if (!ans.empty()) ans[0]=ans[0]-'a'+'A';
cout<<"Stage: "<<ans;
return 0;
}
H. Permutation
关键点基本都想到了，结果最后犯病了分界点求的偏小了一直挂到比赛结束
考虑一个 naive 的二分做法，假设答案在 \([l,r]\) 内，我们先求出次大值所在的位置 \(smx\)
若 \(smx\in[l,mid]\)，则我们询问 \([l,mid]\)，若返回值仍为 \(smx\) 则说明 \(n\) 一定在 \([l,mid]\) 中，此时可以继续利用当前询问的值，下次就不用先问整个区间的次大值了，否则询问 \([mid+1,r]\)，要多一次询问；\(smx\in[mid+1,r]\) 的情况同理
但这样最坏情况下询问次数会达到 \(2\log_2 n\) 级别，因此要考虑优化，而题目中给出的 \(1.5\log_2 n\) 的界感觉就是要用不均匀分割
考虑令 \(f(x)\) 表示长度为 \(x\) 的区间至少要问多少次，不难根据上述做法写出转移式：
\[f(x)=\min_\limits{1\le y\le x-1} \max(f(y)+1,f(x-y)+2) \]写个暴力转移 check 一下会发现这个东西求出的值恰好被上界 bound 住，但朴素的 DP 转移是 \(O(n^2)\) 的
考虑快速求出最优转移点，由于 \(\max\) 两部分都是单调的，因此最优解一定在 tradeoff 的时候取得
不妨设最优转移点对应的 \(\frac{y}{x}=\theta\)，直接把 \(f(x)=1.5\log_2 x\) 带进 \(f(\theta\cdot x)+1=f((1-\theta)\cdot x)+2\) 中解得 \(\theta = \frac{2^{\frac{2}{3}}}{1+2^{\frac{2}{3}}}\)，这样我们每次 DP 的时候在这附近取转移点即可
最后实测可以卡着上界通过，据说正解好像是用黄金分割比来推的说
#include<cstdio>
#include<iostream>
#include<cmath>
#include<map>
#include<cassert>
#define RI register int
#define CI const int&
using namespace std;
const int N=1000000;
const double alpha=pow(2.0,2.0/3.0);
const double theta=alpha/(1.0+alpha);
int t,n,cnt,sum,f[N+5],pos[N+5]; map <pair <int,int>,int> rst;
inline int ask(CI l,CI r)
{
assert(r-l+1>=2);
if (rst.count({l,r})) return rst[{l,r}];
printf("? %d %d\n",l,r); fflush(stdout);
++cnt; sum+=r-l+1;
int res; scanf("%d",&res); return rst[{l,r}]=res;
}
inline void answer(CI p)
{
printf("! %d\n",p); fflush(stdout);
}
int main()
{
f[1]=0; f[2]=1;
for (RI i=3;i<=N;++i)
{
int st=max(1,(int)(theta*i)-1);
pos[i]=st; f[i]=max(f[st],f[i-st]+1)+1;
for (RI j=1;j<=3;++j)
{
int y=min(st+j,i-1);
int tmp=max(f[y],f[i-y]+1)+1;
if (tmp<=f[i]) f[i]=tmp,pos[i]=y;
}
}
//for (RI i=1;i<=N;++i) assert(f[i]<=(int)ceil(1.5L*log2(i)));
// for (RI i=3;i<=20;++i) printf("%d %d\n",i,pos[i]);
for (scanf("%d",&t);t;--t)
{
scanf("%d",&n); rst.clear(); cnt=0; sum=0;
int l=1,r=n;
while (r-l+1>2)
{
int smx=ask(l,r),len=pos[r-l+1];
if (smx<=l+len-1)
{
int tmp=ask(l,l+len-1);
if (smx==tmp) r=l+len-1; else l+=len;
} else
{
int tmp=ask(r-len+1,r);
if (smx==tmp) l=r-len+1; else r-=len;
}
}
assert(l<=r);
if (l==r) answer(l); else
{
int tmp=ask(l,r);
if (tmp==l) answer(r); else answer(l);
}
assert(cnt<=(int)ceil(1.5L*log2(n)));
assert(sum<=3*n);
}
return 0;
}
I. Piggy Sort
看题解好像不难的一个题，大致思路就是用抽屉原理发现枚举前两张照片中的点对确定一条直线后可以直接确定一只猪，后面交给祁神去补了
J. Even or Odd Spanning Tree
首先不难发现求出一个 MST 后其中一个答案就确定了
根据单峰性，很容易发现替换一条边是最优的，即我们枚举一条不在生成树上的边 \((u,v,w)\)，在生成树上找到一条权值奇偶性与 \(w\) 不同，且权值最大的边替换，倍增一下即可
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<array>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=500005,INF=1e18;
int t,n,m,fa[N],dep[N],anc[N][20],mx[N][20][2];
array <int,3> E[N]; vector <pair <int,int>> T[N];
inline int getfa(CI x)
{
return fa[x]!=x?fa[x]=getfa(fa[x]):x;
}
inline void DFS(CI now=1,CI fa=0)
{
dep[now]=dep[fa]+1; anc[now][0]=fa;
for (RI i=0;i<19;++i)
if (anc[now][i])
{
anc[now][i+1]=anc[anc[now][i]][i];
for (RI j=0;j<2;++j) mx[now][i+1][j]=max(mx[now][i][j],mx[anc[now][i]][i][j]);
} else break;
for (auto [to,w]:T[now]) if (to!=fa)
{
mx[to][0][w&1]=w; mx[to][0][(w&1)^1]=-INF;
DFS(to,now);
}
}
inline int query(int x,int y,CI tp,int ret=-INF)
{
if (dep[x]<dep[y]) swap(x,y);
for (RI i=19;i>=0;--i) if (dep[anc[x][i]]>=dep[y])
ret=max(ret,mx[x][i][tp]),x=anc[x][i];
if (x==y) return ret;
for (RI i=19;i>=0;--i) if (anc[x][i]!=anc[y][i])
ret=max(ret,max(mx[x][i][tp],mx[y][i][tp])),x=anc[x][i],y=anc[y][i];
return max(ret,max(mx[x][0][tp],mx[y][0][tp]));
}
signed main()
{
for (scanf("%lld",&t);t;--t)
{
scanf("%lld%lld",&n,&m);
for (RI i=0;i<=n;++i) for (RI j=0;j<20;++j) anc[i][j]=0;
for (RI i=1;i<=m;++i) scanf("%lld%lld%lld",&E[i][1],&E[i][2],&E[i][0]);
sort(E+1,E+m+1); vector <array <int,3>> Rep;
for (RI i=1;i<=n;++i) fa[i]=i,T[i].clear();
int sum1=0,cnt=0;
for (RI i=1;i<=m;++i)
{
auto [w,u,v]=E[i];
if (getfa(u)==getfa(v))
{
Rep.push_back(E[i]); continue;
}
fa[getfa(u)]=getfa(v); sum1+=w; ++cnt;
T[u].push_back({v,w}); T[v].push_back({u,w});
}
if (cnt!=n-1)
{
puts("-1 -1"); continue;
}
int sum2=INF; DFS();
for (auto [w,u,v]:Rep)
{
int ww=query(u,v,(w&1)^1);
if (ww!=-INF) sum2=min(sum2,sum1-ww+w);
}
if (sum1&1) swap(sum1,sum2);
if (sum1==INF) sum1=-1;
if (sum2==INF) sum2=-1;
printf("%lld %lld\n",sum1,sum2);
}
return 0;
}
M. Triangles
算出初始时总三角形数后，容斥减去经过被删除的边的三角形即可，简单推一推式子
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, a, b; cin >> n >> a >> b;
int tot = 0;
for (int i=1; i<=n; ++i) {
tot += (n-i+2)*(n-i+1)/2;
if (n-i >= i) tot += (n-2*i+2)*(n-2*i+1)/2;
}
tot -= b*(a+1-b);
int res = 0;
for (int i=1; i<=min(n-a, a); ++i) {
res += min(a, b+i-1) - max(b-i, 0LL) + 1 - i;
}
tot -= res;
cout << tot << '\n';
return 0;
}
Postscript
今天直接被大一小登薄纱了，看来是离入土不远了
标签：const,int,Universal,Cangqian,define,return,include,RI,Stage From： https://www.cnblogs.com/cjjsb/p/18445813