Preface
今天由于是我们队搬毒瘤场，因此下午就不用集中训练索性继续 VP UCup
这场题很有外国场的风格，代码量和科技含量都不大，只要动动脑筋就行了，最后也是刚好打到了 10 题下班
A. Aliases
不难发现假设 \(a=b=0\)，则 \(c\le \log_{10} n\le 7\)，因此只要考虑 \(a+b+c\le 7\) 的情况，直接枚举即可
#include<cstdio>
#include<iostream>
#include<string>
#include<map>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int t,n,pw[10]; string A[N],B[N];
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
RI i; for (pw[0]=i=1;i<=7;++i) pw[i]=pw[i-1]*10;
for (cin>>t;t;--t)
{
for (cin>>n,i=1;i<=n;++i) cin>>A[i]>>B[i];
for (RI sum=1;sum<=7;++sum)
{
for (RI a=0;a<=sum;++a)
for (RI b=0;a+b<=sum;++b)
{
int c=sum-a-b,mx=0; map <string,int> rst;
for (i=1;i<=n;++i)
{
string tmp=A[i].substr(0,a)+B[i].substr(0,b);
mx=max(mx,++rst[tmp]);
if (mx>pw[c]) break;
}
if (mx<=pw[c])
{
cout<<a<<' '<<b<<' '<<c<<'\n';
goto exit;
}
}
}
exit:;
}
return 0;
}
B. Bars
这题在去年的 2023年电子科技大学ACM-ICPC暑假前集训-数学 里做过，因此直接贴当时写的题解了
首先考虑朴素的DP做法，不难想到设\(f_i\)表示\(i\)位置为关键点，\([1,i]\)这些位置能得到的最大价值
转移的时候就是枚举上一个关键点\(j\)，此时\([j,i-1]\)中这些位置的右边第一个关键点都是\(a_i\)，且\([j+1,i]\)这些位置的左边第一个关键点都是\(a_j\)
因此不难写出转移方程：
\[f_i=\max_\limits{j<i} f_j+(i-j)\times (a_i+a_j) \]这种DP方程第一眼考虑决策单调性或者斜率优化，但实操一下会发现没法处理，因为既有\(j\times a_i\)的项，也有\(i\times a_j\)的项
看似走投无路了，但根据不那么显然的观察可以看出，\((i-j)\times (a_i+a_j)\)是以\((i,0).(i,a_i),(j,0),(j,a_j)\)四点构成的梯形面积的两倍
因此我们可以把原题意转化为，给定平面上的若干点\((i,a_i)\)，求它们与\(x\)轴形成的最大面积的多边形
那么很显然就是求这些点构成的凸包即可，直接单调栈搞一波，复杂度\(O(n)\)
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5+5;
struct Pt{
int x, y;
int crs(const Pt &b)const{return x*b.y-y*b.x;}
Pt operator-(const Pt &b)const{return Pt{x-b.x, y-b.y};}
}pt[N];
int cross(Pt p, Pt a, Pt b){return (a-p).crs(b-p);}
int t, n, A[N];
Pt stk[N]; int tp=0;
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
cin >> t;
while (t--){
cin >> n;
for (int i=1; i<=n; ++i) cin >> A[i], pt[i]=Pt{i, A[i]};
tp=-1;
stk[++tp] = pt[1];
stk[++tp] = pt[2];
for (int i=3; i<=n; ++i){
while (tp>0 && cross(stk[tp-1], stk[tp], pt[i])>=0) --tp;
stk[++tp] = pt[i];
}
// for (int i=0; i<=tp; ++i) printf("(%lld %lld)\n", stk[i].x, stk[i].y);
int ans=0;
for (int i=1; i<=tp; ++i){
ans += (stk[i-1].y+stk[i].y)*(stk[i].x-stk[i-1].x);
}
cout << ans << '\n';
}
return 0;
}
C. Ctrl+C Ctrl+V
签到，令 \(f_{i,mask}\) 表示处理了前 \(i\) 位，从第 \(i\) 位往前的 \(mask\) 状态是否被修改，转移十分显然
#include<cstdio>
#include<iostream>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
const int N=1e6+5,INF=1e9;
int t,f[N][1<<4]; char s[N];
int main()
{
for (scanf("%d",&t);t;--t)
{
RI i,j,k; scanf("%s",s+1); int n=strlen(s+1);
if (n<=3) { puts("0"); continue; }
for (i=1;i<=n;++i) for (j=0;j<16;++j) f[i][j]=INF;
for (j=0;j<16;++j) f[4][j]=__builtin_popcount(j);
if (s[1]=='a'&&s[2]=='n'&&s[3]=='i'&&s[4]=='a') f[4][0]=INF;
for (i=4;i<n;++i) for (j=0;j<16;++j) if (f[i][j]!=INF)
{
for (k=0;k<2;++k)
{
int mask=((j<<1)&15)|k;
if (mask==0&&s[i-2]=='a'&&s[i-1]=='n'&&s[i]=='i'&&s[i+1]=='a') continue;
f[i+1][mask]=min(f[i+1][mask],f[i][j]+k);
}
}
int ans=INF; for (j=0;j<16;++j) ans=min(ans,f[n][j]);
printf("%d\n",ans);
}
return 0;
}
D. Dazzling Mountain
签到，对于每个点 \(x\)，求出其子树大小 \(sz_x\)，然后用一个桶判断下每种 \(sz\) 对应的叶子数量是否等于总数即可
#include<cstdio>
#include<iostream>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
const int N=1e6+5;
int t,n,x,y,leaf,l[N],sz[N],bkt[N]; vector <int> v[N];
inline void DFS(CI now=1,CI fa=0)
{
l[now]=0; sz[now]=1;
for (auto to:v[now]) if (to!=fa)
DFS(to,now),l[now]+=l[to],sz[now]+=sz[to];
if (sz[now]==1) ++l[now],++leaf;
bkt[sz[now]]+=l[now];
}
int main()
{
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%d",&n),i=1;i<=n;++i) v[i].clear(),bkt[i]=0;
for (i=1;i<n;++i) scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
vector <int> ans; leaf=0;
for (DFS(),i=1;i<=n;++i) if (bkt[i]==leaf) ans.push_back(i);
//for (i=1;i<=n;++i) printf("%d %d\n",sz[now],l[now]);
printf("%d\n",ans.size());
for (auto x:ans) printf("%d ",x); putchar('\n');
}
return 0;
}
E. Euclidean Algorithm
想到关键就很简单的一个题
首先要注意到 \(2a-b\) 的变化可以看作在数轴上有若干个点，每次可以把某个点 \(b\) 作关于另一个点 \(a\) 的对称点
不难发现无论怎么操作任意两点之间的距离都不会缩小，最小值就是初始时的 \(b-a\)
因此有解的充要条件就是 \(\gcd(a,b)=a\bmod (b-a)\)，统计合法的方案数也非常套路
不妨先钦定 \(\gcd(a,b)=1\) 对应的答案为 \(f(x)\)，则最后答案为 \(\sum_{i=1}^n f(\lfloor\frac{n}{i}\rfloor)\)
满足 \(1=a\bmod (b-a)\) 的对数也很好计算，枚举 \(b-a\) 的值 \(j\)，则画画图会发现只有 \(\lfloor\frac{x-1}{j}\rfloor\) 种方案，则 \(f(x)=\sum_{j=1}^{x-1} \lfloor\frac{x-1}{j}\rfloor\)
用除法分块套除法分块，时间复杂度 \(O(n^{\frac{3}{4}})\)，由于时限很大可以通过（跑了 24531ms）
#include<cstdio>
#include<iostream>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
int t,n;
inline void write(const __int128& x)
{
if (x>=10) write(x/10); putchar(x%10+'0');
}
signed main()
{
for (scanf("%lld",&t);t;--t)
{
scanf("%lld",&n); __int128 ans=0;
auto f=[&](int n)
{
__int128 ret=0; --n;
for (int l=1,r;l<=n;l=r+1)
r=n/(n/l),ret+=__int128(r-l+1)*(n/l);
return ret;
};
for (int l=1,r;l<=n;l=r+1)
r=n/(n/l),ans+=__int128(r-l+1)*f(n/l);
write(ans); putchar('\n');
}
return 0;
}
F. Flower Garden
感觉不太可做，弃疗
G. Great Chase
这题祁神看了眼就秒了，我题意都不知道
#include<bits/stdc++.h>
using namespace std;
#define int long long
using LD = long double;
const LD eps = 1e-8;
int sgn(LD x){return fabs(x)<=eps ? 0 : (x>eps ? 1 : -1);}
const int N = 4e5+5;
int t, n, p[N], v[N];
const LD INF = 1e18;
bool check(LD x){
LD mx=-INF, mn=INF;
for (int i=1; i<=n; ++i){
if (p[i]>0) mn=min(mn, p[i]-v[i]*x);
else mx=max(mx, p[i]+v[i]*x);
}
return sgn(mx-mn)<0;
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
cout << setiosflags(ios::fixed) << setprecision(10);
cin >> t;
while (t--){
cin >> n >> v[0];
for (int i=1; i<=n; ++i) cin >> p[i] >> v[i];
LD L=0.0L, R=1e13;
for (int tt=0; tt<200; ++tt){
// printf("L=%Lf R=%Lf\n", L, R);
LD M = (R+L)*0.5L;
if (check(M)) L=M;
else R=M;
}
cout << L*v[0] << '\n';
}
return 0;
}
H. Hyperloop
看起来也是个神仙题，弃疗
I. Investors
没有证明，全是猜测，但就是能过题.jpg
首先直觉告诉我们这个问题等价于把原序列分成 \(k+1\) 段，每段之间不会相互影响，因此总逆序对数量就是所有段逆序对数量之和
大力 DP 复杂度显然是 \(O(n^3)\) 的，但这种分段类的 DP 一般肯定会有决策单调性，懒得证明了直接爬上去写完就过了
由于这场没有题解我也不知道这玩意咋证的，总之能过就行，复杂度 \(O(n^2\log n)\)
#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=6005,INF=1e9;
int t,n,m,k,a[N],rst[N],g[N][N],f[N][N];
class Tree_Array
{
private:
int bit[N];
public:
#define lowbit(x) (x&-x)
inline int get(RI x,int ret=0)
{
for (;x<=m;x+=lowbit(x)) ret+=bit[x]; return ret;
}
inline void add(RI x,CI y)
{
for (;x;x-=lowbit(x)) bit[x]+=y;
}
#undef lowbit
}BIT;
inline void solve(CI k,CI l=1,CI r=n,CI L=1,CI R=n)
{
if (l>r) return; int mid=l+r>>1,pos;
for (RI i=L;i<=R&&i<=mid;++i)
if (f[k-1][i-1]+g[i][mid]<f[k][mid])
f[k][mid]=f[k-1][i-1]+g[i][mid],pos=i;
solve(k,l,mid-1,L,pos); solve(k,mid+1,r,pos,R);
}
int main()
{
for (scanf("%d",&t);t;--t)
{
RI i,j; for (scanf("%d%d",&n,&k),i=1;i<=n;++i)
scanf("%d",&a[i]),rst[i]=a[i];
sort(rst+1,rst+n+1); m=unique(rst+1,rst+n+1)-rst-1;
for (i=1;i<=n;++i) a[i]=lower_bound(rst+1,rst+m+1,a[i])-rst;
for (i=1;i<=n;++i)
{
g[i][i]=0; BIT.add(a[i],1);
for (j=i+1;j<=n;++j)
g[i][j]=g[i][j-1]+BIT.get(a[j]+1),BIT.add(a[j],1);
for (j=i;j<=n;++j) BIT.add(a[j],-1);
}
for (++k,i=1;i<=n;++i) f[1][i]=g[1][i];
for (i=2;i<=k;++i)
{
for (j=1;j<=n;++j) f[i][j]=INF;
solve(i);
}
printf("%d\n",f[k][n]);
}
return 0;
}
J. Job for a Hobbit
看起来是防 AK 题，弃疗
K. Kooky Tic-Tac-Toe
大力模拟题，由于我们队开场开题顺序有问题所以导致罚时极其抽象，因此定下铁律如果有人开场 1h 内上机写了 100 行以上的东西就自动下机
具体判断时可以枚举最后下的一颗棋子，使得拿去这颗子后游戏不结束，但细节还是比较多的
#include<bits/stdc++.h>
using namespace std;
const int N = 10;
int t, n, k;
struct Node{
string tbl[N];
};
using pii = pair<int, int>;
int calc(Node &cur, int r, int c, int dr, int dc){
int res=1;
for (int x=1; x<=n; ++x){
int nr=r+dr*x, nc=c+dc*x;
if (nr<=0 || nr>n || nc<=0 || nc>n) break;
if (cur.tbl[nr][nc]!=cur.tbl[r][c]) break;
++res;
}
return res;
}
pii findChain(Node &cur){
int anso=0, ansx=0;
for (int i=1; i<=n; ++i){
for (int j=1; j<=n; ++j){
if ('.'==cur.tbl[i][j]) continue;
if ('o'==cur.tbl[i][j]){
anso = max(anso, calc(cur, i, j, 0, 1));
anso = max(anso, calc(cur, i, j, 1, 0));
anso = max(anso, calc(cur, i, j, 1, 1));
anso = max(anso, calc(cur, i, j, 1, -1));
}
if ('x'== cur.tbl[i][j]){
ansx = max(ansx, calc(cur, i, j, 0, 1));
ansx = max(ansx, calc(cur, i, j, 1, 0));
ansx = max(ansx, calc(cur, i, j, 1, 1));
ansx = max(ansx, calc(cur, i, j, 1, -1));
}
}
}
return {anso, ansx};
}
void genMove(vector<pii> &res, Node &cur, char ch){
vector<pii> vec1, vec2;
for (int i=1; i<=n; ++i) for (int j=1; j<=n; ++j){
if ('.'==cur.tbl[i][j]) continue;
if (ch==cur.tbl[i][j]) vec1.emplace_back(i, j);
else vec2.emplace_back(i, j);
}
res.clear();
for (int i=0; i<(int)vec1.size(); ++i){
res.push_back(vec1[i]);
if (i<vec2.size()) res.push_back(vec2[i]);
}
}
void solve(){
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
cin >> t;
while (t--){
Node nd;
cin >> n >> k;
// printf("n=%d k=%d\n", n, k);
for (int i=1; i<=n; ++i){
cin >> nd.tbl[i];
nd.tbl[i] = '$' + nd.tbl[i];
}
int cntx=0, cnto=0, cntd=0;
for (int i=1; i<=n; ++i) for (int j=1; j<=n; ++j){
if ('o'==nd.tbl[i][j]) ++cnto;
else if ('x'==nd.tbl[i][j]) ++cntx;
else ++cntd;
}
if (abs(cntx-cnto)>1){
cout << "NIE\n";
continue;
}
auto [anso, ansx] = findChain(nd);
bool ok=true;
if (ansx>=k && anso>=k) ok=false;
if (ansx>=2*k || anso>=2*k) ok=false;
if (!ok) cout << "NIE\n";
else{
char winner='.';
if (ansx>=k) winner='x';
if (anso>=k) winner='o';
if ('.'==winner){
if (0==cntd){
vector<pii> res;
genMove(res, nd, (cntx>cnto ? 'x' : 'o'));
cout << "TAK\n";
for (auto [x, y] : res){
cout << x << ' ' << y << '\n';
}
}else cout << "NIE\n";
}else if (('o'==winner && cnto<cntx) || ('x'==winner && cntx<cnto)){
cout << "NIE\n";
}else{
ok=false;
int ar, ac;
Node nxt;
for (int i=1; i<=n; ++i){
for (int j=1; j<=n; ++j){
if (winner==nd.tbl[i][j]){
nxt=nd;
nxt.tbl[i][j]='.';
auto [lo, lx] = findChain(nxt);
if (lo<k && lx<k){
ar=i, ac=j;
ok=true; break;
}
}
}
if (ok) break;
}
if (!ok) cout << "NIE\n";
else{
vector<pii> res;
char ch;
if (cntx!=cnto){
ch = (cntx>cnto ? 'x' : 'o');
}else{
ch = (winner=='o' ? 'x' : 'o');
}
genMove(res, nxt, ch);
cout << "TAK\n";
for (auto [x, y] : res){
cout << x << ' ' << y << '\n';
}
cout << ar << ' ' << ac << '\n';
}
}
}
}
return 0;
}
L. Line Replacements
很有思维含量的一个题
首先考虑倒着处理，把删边变成加边，再次之前先判断给出的森林是否合法
显然对于每个联通块，叶子节点必须都是加油站，而中间的非加油站节点的判定就需要思考一下
对于某个非加油站节点，设与其相邻的所有边的权值和为 \(sum\)，显然 \(sum\) 必须为偶数
同时令这些边中边权最大的为 \(mxval\)，若 \(mxval>\frac{sum}{2}\) 则一定无解
再考虑集合中的边，在加入一条两段不同时为加油站的边时，首先要满足加入的边边权为偶数，其次要满足当前加入的边的边权不超过此时这个点相邻的边权和
不难发现加边时的限制和判断原联通块合法的限制是一体两面的，而加边的策略也很简单，就是按照边权从小到大排序即可
#include <bits/stdc++.h>
std::vector<int> work() {
int n, p;
std::cin >> n >> p;
std::vector<bool> hkr(n, false);
std::vector<int64_t> hbk(n, 0);
std::vector<int> deg(n, 0);
std::vector<std::array<int, 3>> edge(n - 1);
for(int i = 0, s; i < p; ++i) std::cin >> s, hkr[s - 1] = true;
for(int i = 0; i < n - 1; ++i) {
auto &[f, t, val] = edge[i];
std::cin >> f >> t >> val;
deg[--f]++, deg[--t]++;
}
int k; std::cin >> k;
std::vector<int> ars(k);
std::vector<bool> dld(n - 1, false);
for(auto &ars: ars) std::cin >> ars, dld[--ars] = true;
for(int i = 0; i < n - 1; ++i) if(dld[i]) {
auto [f, t, _] = edge[i];
deg[f]--, deg[t]--;
} else {
auto [f, t, v] = edge[i];
hbk[f] += v, hbk[t] += v;
}
for(int i = 0; i < n; ++i) if(!hkr[i] && (deg[i] == 1 || hbk[i] % 2 == 1)) return {};
// for(int i = 0; i < n; ++i) std::cout << hbk[i] << char(i == n - 1 ? 10 : 32);
for(int i = 0; i < n - 1; ++i) if(!dld[i]) {
auto [f, t, v] = edge[i];
if(v + v > hbk[f] && !hkr[f] || v + v > hbk[t] && !hkr[t]) return {};
}
// std::cout << "Blyat\n";
std::sort(ars.begin(), ars.end(), [&](const int &x, const int &y) {
return edge[x][2] < edge[y][2];
});
for(int i = 0; i < ars.size(); ++i) {
auto [f, t, v] = edge[ars[i]];
dld[i] = false;
if(hkr[f] && hkr[t]) continue;
if(v % 2) return {};
for(auto c: (int[2]){f, t}) if(!hkr[c]) {
if(v > hbk[c]) return {};
hbk[c] += v;
}
}
std::reverse(ars.begin(), ars.end());
return ars;
}
int main() {
std::ios::sync_with_stdio(false);
int z; std::cin >> z; while(z--) {
auto ans = work();
if(ans.empty()) std::cout << "NIE\n";
else {
std::cout << "TAK\n";
for(int i = 0; i < ans.size(); ++i) std::cout << ans[i] + 1 << char(i == ans.size() - 1 ? 10 : 32);
}
}
return 0;
}
M. Minor Evil
注意到同样可以倒着处理，将杀人改为复活，则显然若从后往前的某天可以复活一个人，则这个人被复活一定是最优的
#include <bits/stdc++.h>
int main() {
std::ios::sync_with_stdio(false);
int z; std::cin >> z; while(z--) {
int n, k; std::cin >> n >> k;
std::vector<bool> alive(n, true);
std::vector<std::pair<int, int>> edge(k);
for(auto &[f, t]: edge) {
std::cin >> f >> t;
f--, t--;
}
int s; std::cin >> s;
for(int i = 0, si; i < s; ++i) {
std::cin >> si;
alive[--si] = false;
}
std::string ans(k, 'N');
for(int i = k - 1; ~i; --i) {
auto [a, b] = edge[i];
if(alive[a] && !alive[b]) {
ans[i] = 'T';
alive[b] = true;
}
}
int i;
for(i = 0; i < n; ++i) if(!alive[i]) {
std::cout << "NIE\n";
break;
}
if(i == n) std::cout << "TAK\n" << ans << char(10);
}
return 0;
}
Postscript
这就是神秘外国场啊，打完一扫前两天每天几个题的阴霾，瞬间找回自信
标签：std,const,AMPPZ,Contest,int,cin,--,2022,include From： https://www.cnblogs.com/cjjsb/p/18308309