Preface
唉感觉最近把把红温负作用啊，这场就中期写 05 被卡常了就红温了一整场，放着更简单的题不写就疯狂乱搞
结果不出所料地被打爆了，只能说是好似，赛后发现甚至有个题是去年一轮的原，结果比赛的时候没一个人看题意，属实绷不住了
感觉现在每场的策略和心态都有很大问题啊，不把这些问题改过来感觉只会越打心态越爆炸
Array-Gift
不难发现操作次数 \(\in\{n-1,n,n+1\}\)，\(n-1\) 的情况很简单，当且仅当序列的 \(\gcd\) 等于其最小值；而 \(n+1\) 是很容易构造出的上界，因此难点在于判断何时取得 \(n\)
很容易想到枚举经过操作一处理了两个位置再检验剩下部分，同时枚举每个数尝试进行操作二再检验剩下部分，然后交上去会发现 WA 了而且想了很久找不到问题
后面手玩了半天发现可能先消去某些数，再进行这一次操作，加上这种 Case 的特判后就可以通过了
#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
int gcd(int a, int b){return 0==b ? a : gcd(b, a%b);}
pii find(const vector<int> &vec){
int sz=vec.size();
int G=vec[0], mn=vec[0];
for (int i=1; i<sz; ++i) G=gcd(G, vec[i]), mn=min(mn, vec[i]);
if (0==mn) {
G=vec[1]; mn=vec[1];
for (int i=2; i<sz; ++i) G=gcd(G, vec[i]), mn=min(mn, vec[i]);
}
return {G, mn};
}
int n;
void solve(){
cin >> n;
vector<int> A(n);
for (int i=0; i<n; ++i) cin >> A[i];
if (1==n){
cout << 0 << '\n';
return;
}
{
auto [G, mn] = find(A);
if (G==mn){ cout << n-1 << '\n'; return; }
}
bool ok=false;
for(int i = 0; i < n; ++i) {
std::vector<int> B;
for(int j = 0; j < n; ++j) if(A[j] % A[i] != 0) B.push_back(A[j]);
auto [G, mn] = find(B);
if(G == mn || A[i] < G) { ok = true; break; }
for(int j = 0; j < n; ++j) {
B.push_back(A[i] % A[j]);
auto [G, mn] = find(B);
if(G == mn) {
ok = true; goto __break__;
}
B.pop_back();
}
}
__break__:
cout << (ok ? n : n+1) << '\n';
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int t; cin >> t; while (t--) solve();
return 0;
}
树论（一）
难点在于分析有用的数对数量是 \(O(n\log^2 n)\) 级别的，证明的话可以参考官方题解
有了这个后很容易想到离线，对于一个点对 \((x,y)\) 把贡献挂在 \(\operatorname{LCA}(x,y)\) 上，然后查询的时候做一个子树和即可
用欧拉序+ ST 表处理 LCA，树状数组维护贡献，总复杂度 \(O(n\log^2 n+q\log n)\)
#include<cstdio>
#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
typedef pair <int,int> pi;
const int N=100005;
int t,n,x,y,q,ans[N*10]; vector <int> v[N];
vector <pi> vec[N]; vector <pi> ques[N];
inline void init(CI n)
{
for (RI g=1;g<=n;++g)
{
for (RI i=g;i<=n;i+=g)
for (RI j=g;g<=n&&i/g*j<=n&&j<=i;j+=g)
if (__gcd(i,j)==g) vec[i/g*j].push_back(pi(j,i));
}
}
namespace LCA_Solver
{
const int NN=200005;
int dep[NN],seq[NN],fir[NN],idx,L[NN],R[NN],cnt,mxd[NN][20],_log[NN];
inline void DFS(CI now=1,CI fa=0)
{
seq[++idx]=now; dep[now]=dep[fa]+1; fir[now]=idx; L[now]=++cnt;
for (auto to:v[now]) if (to!=fa) DFS(to,now),seq[++idx]=now; R[now]=cnt;
}
inline int mindep(CI x,CI y)
{
return dep[x]<dep[y]?x:y;
}
inline void init_RMQ(CI n)
{
_log[0]=-1; for (RI i=1;i<=n;++i) _log[i]=_log[i>>1]+1;
for (RI i=1;i<=n;++i) mxd[i][0]=seq[i];
for (RI j=1;(1<<j)<=n;++j)
for (RI i=1;i+(1<<j)-1<=n;++i)
mxd[i][j]=mindep(mxd[i][j-1],mxd[i+(1<<j-1)][j-1]);
}
inline int LCA(int x,int y)
{
x=fir[x]; y=fir[y]; if (x>y) swap(x,y);
int k=_log[y-x+1]; return mindep(mxd[x][k],mxd[y-(1<<k)+1][k]);
}
}
using namespace LCA_Solver;
class Tree_Array
{
private:
int bit[N];
public:
#define lowbit(x) (x&-x)
inline void clear(void)
{
for (RI i=0;i<=n;++i) bit[i]=0;
}
inline void add(RI x,CI y)
{
for (;x<=n;x+=lowbit(x)) bit[x]+=y;
}
inline int get(RI x,int ret=0)
{
for (;x;x-=lowbit(x)) ret+=bit[x]; return ret;
}
inline int query(CI l,CI r)
{
return get(r)-get(l-1);
}
#undef lowbit
}BIT;
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
for (cin>>t,init(100000);t;--t)
{
cin>>n; for (RI i=1;i<=n;++i) v[i].clear();
for (RI i=1;i<n;++i) cin>>x>>y,v[x].push_back(y),v[y].push_back(x);
idx=cnt=0; DFS(); init_RMQ(idx); BIT.clear();
for (RI i=1;i<=100000;++i) ques[i].clear();
cin>>q; for (RI i=1;i<=q;++i) ans[i]=0,cin>>x>>y,ques[y].push_back(pi(x,i));
for (RI i=1;i<=100000;++i)
{
for (auto [x,y]:vec[i])
if (y<=n) BIT.add(L[LCA(x,y)],x!=y?2:1);
for (auto [x,id]:ques[i]) ans[id]=BIT.query(L[x],R[x]);
}
for (RI i=1;i<=q;++i) cout<<ans[i]<<" \n"[i==q];
}
return 0;
}
树论（二）
经典陷入思维定势后就出不来了，然后活活被卡到结束
很容易想到枚举 \(\gcd(x,y)\) 的值 \(g\)，我们标记所有标号为 \(g\) 的倍数的点，建出它们的虚树，很容易发现虚树上的边在原树上对应的路径都可以取 \(g\) 的贡献
直接做复杂度肯定会炸，因此考虑从大到小枚举 \(g\)，同时发现我们不需要显式地建出虚树，只要求出所有点的 \(\operatorname{LCA}\) 然后把这些点到 \(\operatorname{LCA}\) 的路径上的没被赋值的边赋值为 \(g\)
不难想到用并查集优化该过程，使得每条边只会被赋值一次，此时复杂度已经是 \(O(n\log n)\) 的了，但因为常数问题很难卡过
考虑更本质的做法，既然已经想到了用并查集缩边，事实上已经完全没必要求 \(\operatorname{LCA}\) 了，只要每次将两个点之间的树上路径全部操作一次即可
#include<cstdio>
#include<iostream>
#include<vector>
#include<cctype>
#define RI register int
#define CI const int&
#define Tp template <typename T>
using namespace std;
typedef pair <int,int> pi;
const int N=2e6+5;
int t,n,x,y,dep[N],anc[N],lst[N],fa[N],ans[N]; vector <pi> v[N];
class FileInputOutput
{
private:
static const int S=1<<21;
#define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)
#define pc(ch) (Ftop!=Fend?*Ftop++=ch:(fwrite(Fout,1,S,stdout),*(Ftop=Fout)++=ch))
char Fin[S],Fout[S],*A,*B,*Ftop,*Fend; int pt[30];
public:
inline FileInputOutput(void) { Ftop=Fout; Fend=Fout+S; }
Tp inline void read(T& x)
{
x=0; char ch; while (!isdigit(ch=tc()));
while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));
}
Tp inline void write(T x,const char ch='\n')
{
RI ptop=0; while (pt[++ptop]=x%10,x/=10);
while (ptop) pc(pt[ptop--]+48); pc(ch);
}
inline void flush(void)
{
fwrite(Fout,1,Ftop-Fout,stdout);
}
#undef tc
#undef pc
}F;
inline void DFS(CI now=1,CI fa=0)
{
dep[now]=dep[fa]+1;
for (auto [to,id]:v[now]) if (to!=fa) anc[to]=now,lst[to]=id,DFS(to,now);
}
inline int getfa(CI x)
{
return fa[x]!=x?fa[x]=getfa(fa[x]):x;
}
inline void jump(int x,int y,CI z)
{
for (x=getfa(x),y=getfa(y);x!=y;)
{
if (dep[x]<dep[y]) swap(x,y);
ans[lst[x]]=z; fa[x]=getfa(anc[x]); x=fa[x];
}
}
int main()
{
//freopen("1005.in","r",stdin); freopen("05.out","w",stdout);
int size(256<<20); //256M
__asm__ ( "movq %0, %%rsp\n"::"r"((char*)malloc(size)+size));
for (F.read(t);t;--t)
{
F.read(n); for (RI i=1;i<=n;++i) v[i].clear();
for (RI i=1;i<n;++i)
{
F.read(x); F.read(y);
v[x].push_back(pi(y,i)); v[y].push_back(pi(x,i));
}
DFS(); for (RI i=1;i<=n;++i) fa[i]=i;
for (RI i=n/2;i>=1;--i)
for (RI j=i*2;j<=n;j+=i) jump(i,j,i);
for (RI i=1;i<n;++i) F.write(ans[i]," \n"[i==n-1]);
}
F.flush();
exit(0);
return 0;
}
猫罐头游戏
祁神开场写的签，我题意都没看
#include<bits/stdc++.h>
using namespace std;
signed main(){
int t; cin >> t;
while (t--){
int a, b, c; cin >> a >> b >> c;
while (a%2==0 && b%2==0 && c%2==0) a/=2, b/=2, c/=2;
int cnt=0;
if (a%2==0) ++cnt;
if (b%2==0) ++cnt;
if (c%2==0) ++cnt;
if (0==cnt) cout << "NO\n";
else cout << "YES\n";
}
return 0;
}
猫咪们狂欢
很经典的最大权闭合子图模型
首先仅需要考虑两端都是狂欢猫的边，先假设所有的贡献都可以取到
不妨将两颗树上的边看作二分图的两部点，每条边向源/汇点连其边权对应的边，同时将两部点之间有冲突关系的连上容量为 \(\infty\) 的边
不难发现此时图的最小割就是最少要放弃的代价，用总和减去这个值即可
#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
typedef pair <int,int> pi;
const int N=1005,INF=1e9;
int T,n,k,key[N],x,y,z; vector <int> A[N];
namespace Network_Flow
{
const int NN=2005,MM=1e7+5;
struct edge
{
int to,nxt,v;
}e[MM<<1]; int cnt=1,head[NN],cur[NN],dep[NN],s,t;
inline void addedge(CI x,CI y,CI z)
{
//printf("%d -> %d %d\n",x,y,z);
e[++cnt]=(edge){y,head[x],z}; head[x]=cnt;
e[++cnt]=(edge){x,head[y],0}; head[y]=cnt;
}
inline void clear(void)
{
memset(head,0,(t+1)*sizeof(int)); cnt=1;
}
#define to e[i].to
inline bool BFS(void)
{
memset(dep,0,(t+1)*sizeof(int)); dep[s]=1;
queue <int> q; q.push(s);
while (!q.empty())
{
int now=q.front(); q.pop();
for (RI i=head[now];i;i=e[i].nxt)
if (e[i].v&&!dep[to]) dep[to]=dep[now]+1,q.push(to);
}
return dep[t];
}
inline int DFS(CI now,CI tar,int dis)
{
if (now==tar) return dis; int ret=0;
for (RI& i=cur[now];i&&dis;i=e[i].nxt)
if (e[i].v&&dep[to]==dep[now]+1)
{
int dist=DFS(to,tar,min(dis,e[i].v));
if (!dist) dep[to]=0;
dis-=dist; ret+=dist;
e[i].v-=dist; e[i^1].v+=dist;
if (!dis) return ret;
}
if (!ret) dep[now]=0;
return ret;
}
#undef to
inline int Dinic(int ret=0)
{
while (BFS()) memcpy(cur,head,(t+1)*sizeof(int)),ret+=DFS(s,t,INF); return ret;
}
}
using namespace Network_Flow;
int main()
{
for (scanf("%d",&T);T;--T)
{
scanf("%d%d",&n,&k); int idx=0,sum=0;
for (RI i=1;i<=n;++i) A[i].clear(),key[i]=0;
for (RI i=1;i<=k;++i) scanf("%d",&x),key[x]=1;
vector <pi> S,T;
for (RI i=1;i<n;++i)
{
scanf("%d%d%d",&x,&y,&z);
if (key[x]&&key[y])
{
++idx; sum+=z;
S.push_back(pi(idx,z));
A[x].push_back(idx);
A[y].push_back(idx);
}
}
for (RI i=1;i<n;++i)
{
scanf("%d%d%d",&x,&y,&z);
if (key[x]&&key[y])
{
++idx; sum+=z;
T.push_back(pi(idx,z));
for (auto id:A[x]) addedge(id,idx,INF);
for (auto id:A[y]) addedge(id,idx,INF);
}
}
s=idx+1; t=s+1;
for (auto [id,w]:S) addedge(s,id,w);
for (auto [id,w]:T) addedge(id,t,w);
printf("%d\n",sum-Dinic());
clear();
}
return 0;
}
世末农庄
没啥好说的，就是去年一轮做过的题，结果我们队三个做过原题的人没一个看了这题
和原题的唯一区别就是多了操作三，要注意不能之间把这个点点权清空，否则会导致倍增的时候出现问题
一个好的处理方法就是打一个非 \(0\) 的清空标记，如果某次查询找到的点是带标记的点再将其真实地清空即可，总复杂度 \(O(q\log q)\)
#include<cstdio>
#include<iostream>
#include<cstring>
#define RI register int
#define CI const int&
#define mp make_pair
using namespace std;
typedef long long LL;
typedef pair <int,int> pi;
const int N=200005;
int t,q,a[N],c[N],anc[N][20],tp,x,y;
int main()
{
//freopen("1010.in","r",stdin); freopen("10.out","w",stdout);
ios::sync_with_stdio(0); cin.tie(0);
for (cin>>t;t;--t)
{
memset(anc,-1,sizeof(anc));
cin>>q>>c[0]>>a[0];
RI i,j; for (i=1;i<=q;++i)
{
cin>>tp;
if (tp==1)
{
cin>>x>>y; anc[x][0]=y;
cin>>c[x]>>a[x];
for (j=0;j<19;++j) if (~anc[x][j])
anc[x][j+1]=anc[anc[x][j]][j]; else break;
} else if (tp==2)
{
cin>>x>>y; int ret=0; long long tot=0;
while (y>0&&a[x])
{
int top=x; for (j=19;j>=0;--j)
if (~anc[top][j]&&a[anc[top][j]]) top=anc[top][j];
if (a[top]==-1) { a[top]=0; continue; }
int tmp=min(a[top],y); y-=tmp; a[top]-=tmp;
ret+=tmp; tot+=1LL*tmp*c[top];
}
cout<<ret<<' '<<tot<<'\n';
} else cin>>x,a[x]=-1;
}
}
return 0;
}
开关灯
经典看一眼样例猜测答案就是 \(2^n\)，然后需要特判 \(n\le 2\) 的情况，好家伙结果写完还没交就听到旁边同校的队伍交上去 WA 了
遂冷静了一会去写了个爆搜，发现当 \(n\bmod 3=2\) 时需要特判，答案为 \(2^{n-1}\)，加上去就过了
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int mod=998244353;
int t,n;
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
for (cin>>t;t;--t)
{
cin>>n; if (n<=2) puts("2");
else printf("%d\n",quick_pow(2,n%3==2?n-1:n));
}
return 0;
}
飞行棋
不难发现状态有且仅有三种，在 \(0\) 号格、在 \(n\) 号格、在 \(1\sim n-1\) 号格
手推一下状态间的转移关系得答案为 \(\frac{(n-1)^2}{n}+1\)
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int mod=1e9+7;
int t,n;
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
for (cin>>t;t;--t)
cin>>n,cout<<(1LL*(n-1)*(n-1)%mod*quick_pow(n)%mod+1)%mod<<'\n';
return 0;
}
Postscript
就这状态明天还要和 Div.2 的一起训练，不是要被小登吊打
标签：钉耙,const,int,编程,cin,2024,include,RI,define From： https://www.cnblogs.com/cjjsb/p/18339519