想来划划水，结果被打爆了/kk
\((2^k-1)x=n\),枚举\(k\)即可。
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<bitset>
#include<math.h>
#include<stack>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double db;
typedef vector<int> vi;
typedef pair<int,int> pii;
const int N=100000;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define go(u,i) for (register int i=head[u],v=sq[i].to;i;i=sq[i].nxt,v=sq[i].to)
#define fir first
#define sec second
#define mkp make_pair
#define pb push_back
#define maxd 998244353
#define eps 1e-8
inline int read()
{
int x=0,f=1;char ch=getchar();
while ((ch<‘0‘) || (ch>‘9‘)) {if (ch==‘-‘) f=-1;ch=getchar();}
while ((ch>=‘0‘) && (ch<=‘9‘)) {x=x*10+(ch-‘0‘);ch=getchar();}
return x*f;
}
namespace My_Math{
#define N 100000
int fac[N+100],invfac[N+100];
int add(int x,int y) {return x+y>=maxd?x+y-maxd:x+y;}
int dec(int x,int y) {return x<y?x-y+maxd:x-y;}
int mul(int x,int y) {return 1ll*x*y%maxd;}
ll qpow(ll x,int y)
{
ll ans=1;
while (y)
{
if (y&1) ans=mul(ans,x);
x=mul(x,x);y>>=1;
}
return ans;
}
int getinv(int x) {return qpow(x,maxd-2);}
int C(int n,int m)
{
if ((n<m) || (n<0) || (m<0)) return 0;
return mul(mul(fac[n],invfac[m]),invfac[n-m]);
}
void math_init()
{
fac[0]=invfac[0]=1;
rep(i,1,N) fac[i]=mul(fac[i-1],i);
invfac[N]=getinv(fac[N]);
per(i,N-1,1) invfac[i]=mul(invfac[i+1],i+1);
}
#undef N
}
using namespace My_Math;
int main()
{
int T=read();
while (T--)
{
ll n;scanf("%lld",&n);
ll k=3;
while (n>=k)
{
if (n%k==0)
{
printf("%lld\n",n/k);
break;
}
k=k*2+1;
}
}
return 0;
}
\(\frac{n}{2}\)为奇数时显然无解（因为右半边的和为奇数）
否则可进行如\(2,4,\cdots,n,1,3,\cdots,2n-3,x\)的构造，其中\(x\)根据前面的数做差得到。
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<bitset>
#include<math.h>
#include<stack>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double db;
typedef vector<int> vi;
typedef pair<int,int> pii;
const int N=100000;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define go(u,i) for (register int i=head[u],v=sq[i].to;i;i=sq[i].nxt,v=sq[i].to)
#define fir first
#define sec second
#define mkp make_pair
#define pb push_back
#define maxd 998244353
#define eps 1e-8
inline int read()
{
int x=0,f=1;char ch=getchar();
while ((ch<‘0‘) || (ch>‘9‘)) {if (ch==‘-‘) f=-1;ch=getchar();}
while ((ch>=‘0‘) && (ch<=‘9‘)) {x=x*10+(ch-‘0‘);ch=getchar();}
return x*f;
}
namespace My_Math{
#define N 100000
int fac[N+100],invfac[N+100];
int add(int x,int y) {return x+y>=maxd?x+y-maxd:x+y;}
int dec(int x,int y) {return x<y?x-y+maxd:x-y;}
int mul(int x,int y) {return 1ll*x*y%maxd;}
ll qpow(ll x,int y)
{
ll ans=1;
while (y)
{
if (y&1) ans=mul(ans,x);
x=mul(x,x);y>>=1;
}
return ans;
}
int getinv(int x) {return qpow(x,maxd-2);}
int C(int n,int m)
{
if ((n<m) || (n<0) || (m<0)) return 0;
return mul(mul(fac[n],invfac[m]),invfac[n-m]);
}
void math_init()
{
fac[0]=invfac[0]=1;
rep(i,1,N) fac[i]=mul(fac[i-1],i);
invfac[N]=getinv(fac[N]);
per(i,N-1,1) invfac[i]=mul(invfac[i+1],i+1);
}
#undef N
}
using namespace My_Math;
int main()
{
int T=read();
while (T--)
{
int n=read();
if (n%4) {puts("NO");continue;}
else
{
puts("YES");
ll sum=0;
rep(i,1,n>>1)
{
printf("%d ",(i<<1));
sum+=(i<<1);
}
rep(i,1,(n>>1)-1)
{
printf("%d ",i*2-1);
sum-=(i*2-1);
}
printf("%d\n",sum);
}
}
return 0;
}
在每一个同符号的极长连续段中取最大的数即为答案。
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<bitset>
#include<math.h>
#include<stack>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double db;
typedef vector<int> vi;
typedef pair<int,int> pii;
const int N=100000;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define go(u,i) for (register int i=head[u],v=sq[i].to;i;i=sq[i].nxt,v=sq[i].to)
#define fir first
#define sec second
#define mkp make_pair
#define pb push_back
#define maxd 998244353
#define eps 1e-8
inline int read()
{
int x=0,f=1;char ch=getchar();
while ((ch<‘0‘) || (ch>‘9‘)) {if (ch==‘-‘) f=-1;ch=getchar();}
while ((ch>=‘0‘) && (ch<=‘9‘)) {x=x*10+(ch-‘0‘);ch=getchar();}
return x*f;
}
namespace My_Math{
#define N 100000
int fac[N+100],invfac[N+100];
int add(int x,int y) {return x+y>=maxd?x+y-maxd:x+y;}
int dec(int x,int y) {return x<y?x-y+maxd:x-y;}
int mul(int x,int y) {return 1ll*x*y%maxd;}
ll qpow(ll x,int y)
{
ll ans=1;
while (y)
{
if (y&1) ans=mul(ans,x);
x=mul(x,x);y>>=1;
}
return ans;
}
int getinv(int x) {return qpow(x,maxd-2);}
int C(int n,int m)
{
if ((n<m) || (n<0) || (m<0)) return 0;
return mul(mul(fac[n],invfac[m]),invfac[n-m]);
}
void math_init()
{
fac[0]=invfac[0]=1;
rep(i,1,N) fac[i]=mul(fac[i-1],i);
invfac[N]=getinv(fac[N]);
per(i,N-1,1) invfac[i]=mul(invfac[i+1],i+1);
}
#undef N
}
using namespace My_Math;
int n,a[200100];
int calc(int x)
{
if (x>0) return 1;else return -1;
}
int main()
{
int T=read();
while (T--)
{
n=read();
rep(i,1,n) a[i]=read();
ll ans=0,sum=0;
int pos=1,mx=a[1];
rep(i,2,n)
{
if (calc(a[i])==calc(a[pos]))
{
mx=max(mx,a[i]);
}
else
{
ans+=mx;pos=i;mx=a[i];
}
}
ans+=mx;
printf("%lld\n",ans);
}
return 0;
}
枚举\(x\)，求出对每个\(x\)的修改次数。
注意到对一对数\((a,b)(a<b)\).要是想只修改一个数的话必有\(x\in[a+1,b+k]\)，否则就要修改两个数。用一个set维护当前的\(x\)在哪些数对的区间中。
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<bitset>
#include<math.h>
#include<stack>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double db;
typedef vector<int> vi;
typedef pair<int,int> pii;
const int N=1000000+100;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define go(u,i) for (register int i=head[u],v=sq[i].to;i;i=sq[i].nxt,v=sq[i].to)
#define fir first
#define sec second
#define mkp make_pair
#define pb push_back
#define maxd 998244353
#define eps 1e-8
inline int read()
{
int x=0,f=1;char ch=getchar();
while ((ch<‘0‘) || (ch>‘9‘)) {if (ch==‘-‘) f=-1;ch=getchar();}
while ((ch>=‘0‘) && (ch<=‘9‘)) {x=x*10+(ch-‘0‘);ch=getchar();}
return x*f;
}
namespace My_Math{
#define N 100000
int fac[N+100],invfac[N+100];
int add(int x,int y) {return x+y>=maxd?x+y-maxd:x+y;}
int dec(int x,int y) {return x<y?x-y+maxd:x-y;}
int mul(int x,int y) {return 1ll*x*y%maxd;}
ll qpow(ll x,int y)
{
ll ans=1;
while (y)
{
if (y&1) ans=mul(ans,x);
x=mul(x,x);y>>=1;
}
return ans;
}
int getinv(int x) {return qpow(x,maxd-2);}
int C(int n,int m)
{
if ((n<m) || (n<0) || (m<0)) return 0;
return mul(mul(fac[n],invfac[m]),invfac[n-m]);
}
void math_init()
{
fac[0]=invfac[0]=1;
rep(i,1,N) fac[i]=mul(fac[i-1],i);
invfac[N]=getinv(fac[N]);
per(i,N-1,1) invfac[i]=mul(invfac[i+1],i+1);
}
#undef N
}
using namespace My_Math;
int n,k,a[N],sum[N],mn[N];
struct node{int id,l,r;}seg[N];
bool operator <(node p,node q) {return p.r<q.r;}
bool cmp(node p,node q) {return p.l<q.l;}
multiset<node> s;
multiset<node>::iterator it;
vi ask;
int main()
{
int T=read();
while (T--)
{
n=read();k=read();
rep(i,1,n) a[i]=read();
rep(i,1,n>>1)
{
sum[a[i]+a[n-i+1]]++;
int mn=min(a[i],a[n-i+1]),mx=max(a[i],a[n-i+1]);
seg[i]=(node){i,mn+1,mx+k};
}
sort(seg+1,seg+1+(n>>1),cmp);
int ans=n;int pos=1;
rep(x,2,k*2)
{
while (!s.empty())
{
it=s.begin();node tmp=*it;
if (x>tmp.r) s.erase(it);else break;
}
while ((pos<=(n>>1)) && (seg[pos].l==x))
{
s.insert(seg[pos]);pos++;
}
int siz=s.size();
int now=siz-sum[x]+(n/2-siz)*2;
ans=min(ans,now);
}
s.clear();
printf("%d\n",ans);
rep(i,1,k*2) sum[i]=0;
}
return 0;
}
\(a\to b\to c\)的路径可以看成\(a\to b\)和\(c\to b\)的两条，注意到这两条路径在相交后就彼此贴贴重合，于是可以枚举这个相交点，之后再这个点到\(a,b,c\)的路径上贪心的放置权值即可，注意由于到\(b\)的路径要走两次所以要优先放且其贡献需\(\times 2\)。预处理需要分别以\(a,b,c\)为源跑三遍最短路。
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<bitset>
#include<math.h>
#include<stack>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double db;
typedef vector<int> vi;
typedef pair<int,int> pii;
const int N=200000+100;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define go(u,i) for (register int i=head[u],v=sq[i].to;i;i=sq[i].nxt,v=sq[i].to)
#define fir first
#define sec second
#define mkp make_pair
#define pb push_back
#define maxd 998244353
#define eps 1e-8
inline int read()
{
int x=0,f=1;char ch=getchar();
while ((ch<‘0‘) || (ch>‘9‘)) {if (ch==‘-‘) f=-1;ch=getchar();}
while ((ch>=‘0‘) && (ch<=‘9‘)) {x=x*10+(ch-‘0‘);ch=getchar();}
return x*f;
}
namespace My_Math{
#define N 100000
int fac[N+100],invfac[N+100];
int add(int x,int y) {return x+y>=maxd?x+y-maxd:x+y;}
int dec(int x,int y) {return x<y?x-y+maxd:x-y;}
int mul(int x,int y) {return 1ll*x*y%maxd;}
ll qpow(ll x,int y)
{
ll ans=1;
while (y)
{
if (y&1) ans=mul(ans,x);
x=mul(x,x);y>>=1;
}
return ans;
}
int getinv(int x) {return qpow(x,maxd-2);}
int C(int n,int m)
{
if ((n<m) || (n<0) || (m<0)) return 0;
return mul(mul(fac[n],invfac[m]),invfac[n-m]);
}
void math_init()
{
fac[0]=invfac[0]=1;
rep(i,1,N) fac[i]=mul(fac[i-1],i);
invfac[N]=getinv(fac[N]);
per(i,N-1,1) invfac[i]=mul(invfac[i+1],i+1);
}
#undef N
}
using namespace My_Math;
struct node{int to,nxt;}sq[N<<1];
int all=0,head[N];
int n,m,a,b,c,dis[3][N];
bool vis[N];
ll w[N];
struct hnode{int u,dis;};
bool operator <(hnode p,hnode q) {return p.dis>q.dis;}
priority_queue<hnode> q;
void addedge(int u,int v)
{
all++;sq[all].to=v;sq[all].nxt=head[u];head[u]=all;
}
void dij(int st,int *dis)
{
rep(i,1,n) dis[i]=maxd,vis[i]=0;
q.push((hnode){st,0});dis[st]=0;
while (!q.empty())
{
int u=q.top().u;q.pop();
if (vis[u]) continue;vis[u]=1;
go(u,i)
{
if (dis[v]>dis[u]+1)
{
dis[v]=dis[u]+1;
if (!vis[v]) q.push((hnode){v,dis[v]});
}
}
}
}
ll calc(int l,int r)
{
if (r>m) return 1e18;
else return w[r]-w[l-1];
}
int main()
{
int T=read();
while (T--)
{
n=read();m=read();a=read();b=read();c=read();
rep(i,1,m) w[i]=read();
sort(w+1,w+1+m);
rep(i,1,m) w[i]+=w[i-1];
rep(i,1,m)
{
int u=read(),v=read();
addedge(u,v);addedge(v,u);
}
dij(b,dis[0]);dij(a,dis[1]);dij(c,dis[2]);
ll ans=1e18;
rep(i,1,n)
{
int x=dis[0][i],y=dis[1][i],z=dis[2][i];
ll now=calc(1,x)*2+calc(x+1,x+y)+calc(x+y+1,x+y+z);
ans=min(ans,now);
}
printf("%lld\n",ans);
rep(i,1,n) head[i]=0;all=0;
}
return 0;
}
写个dij都调了一万年我菜爆了
差不多想到了但没时间写了，我真是菜啊
注意到当\(r=2\)时其对应的\(l\)必为\(1\)，也就是这个区间的长度为\(2\)，于是我们可以枚举所有长度为\(2\)的区间同时确定\(p_1,p_2\).
如果我们删去所有给定区间中的\(p_1,p_2\), 那么对于\(r=3\)的区间肯定只剩下了\(p_3\)，而对\(r>3\)的区间至少还有两个元素，依次递推下去（在不出现找不到或有多于1个的长度为\(1\)的情况时）就能确定整个排列。而出现上述非法情况时就说明当前枚举的\(p_1,p_2\)是错误的，需要重新枚举。
然而这样还会有一个问题：\(p_1\)与\(p_2\)的相对位置不确定，笔者的处理方法是对题目中所给的区间再重新check一遍。由于每个区间在排列中至多出现一次，所以可以直接暴力check.
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<bitset>
#include<math.h>
#include<stack>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double db;
typedef vector<int> vi;
typedef pair<int,int> pii;
const int N=200+50;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define go(u,i) for (register int i=head[u],v=sq[i].to;i;i=sq[i].nxt,v=sq[i].to)
#define fir first
#define sec second
#define mkp make_pair
#define pb push_back
#define maxd 998244353
#define eps 1e-8
inline int read()
{
int x=0,f=1;char ch=getchar();
while ((ch<‘0‘) || (ch>‘9‘)) {if (ch==‘-‘) f=-1;ch=getchar();}
while ((ch>=‘0‘) && (ch<=‘9‘)) {x=x*10+(ch-‘0‘);ch=getchar();}
return x*f;
}
namespace My_Math{
#define N 100000
int fac[N+100],invfac[N+100];
int add(int x,int y) {return x+y>=maxd?x+y-maxd:x+y;}
int dec(int x,int y) {return x<y?x-y+maxd:x-y;}
int mul(int x,int y) {return 1ll*x*y%maxd;}
ll qpow(ll x,int y)
{
ll ans=1;
while (y)
{
if (y&1) ans=mul(ans,x);
x=mul(x,x);y>>=1;
}
return ans;
}
int getinv(int x) {return qpow(x,maxd-2);}
int C(int n,int m)
{
if ((n<m) || (n<0) || (m<0)) return 0;
return mul(mul(fac[n],invfac[m]),invfac[n-m]);
}
void math_init()
{
fac[0]=invfac[0]=1;
rep(i,1,N) fac[i]=mul(fac[i-1],i);
invfac[N]=getinv(fac[N]);
per(i,N-1,1) invfac[i]=mul(invfac[i+1],i+1);
}
#undef N
}
using namespace My_Math;
int n,len[N],siz[N],ans[N];
bool used[N];
vi a[N];
void out()
{
rep(i,1,n) printf("%d ",ans[i]);puts("");
}
void clr()
{
rep(i,1,n-1) a[i].clear();
}
bool chk()
{
vi tmp;
rep(i,1,n) used[i]=0;
rep(i,1,n-1)
{
int ok=0;
rep(j,1,n-siz[i]+1)
{
tmp.clear();
rep(k,1,siz[i]) tmp.pb(ans[j+k-1]);
sort(tmp.begin(),tmp.end());
if (tmp==a[i])
{
int r=j+siz[i]-1;
if (used[r]) return 0;
used[r]=1;ok=1;break;
}
}
if (!ok) return 0;
}
return 1;
}
bool solve(int id)
{
rep(i,1,n-1)
{
len[i]=siz[i];
}
int x=a[id][0],y=a[id][1];
rep(i,1,n) used[i]=0;
used[x]=used[y]=1;
rep(i,1,n-1)
{
rep(j,0,siz[i]-1)
if ((a[i][j]==x) || (a[i][j]==y)) len[i]--;
}
rep(x,3,n)
{
int pos=0;
rep(i,1,n-1)
{
if (len[i]==1)
{
if (pos) return 0;
pos=i;
}
}
if (!pos) return 0;
int val;
rep(i,0,siz[pos]-1)
if (!used[a[pos][i]]) val=a[pos][i];
if (used[val]) return 0;
ans[x]=val;used[val]=1;
rep(i,1,n-1)
{
rep(j,0,siz[i]-1)
if (a[i][j]==val) len[i]--;
}
}
if (chk()) return 1;else return 0;
}
int main()
{
int T=read();
while (T--)
{
n=read();
rep(i,1,n-1)
{
siz[i]=read();
rep(j,1,siz[i])
{
int x=read();
a[i].pb(x);
}
}
rep(i,1,n-1)
{
if (siz[i]!=2) continue;
ans[1]=a[i][0];ans[2]=a[i][1];
if (solve(i)) {out();break;}
ans[1]=a[i][1];ans[2]=a[i][0];
if (solve(i)) {out();break;}
}
clr();
}
return 0;
}
Codeforces Round #636 (Div. 3) 题解
原文：https://www.cnblogs.com/encodetalker/p/12757960.html