题目链接：https://codeforces.com/contest/985
’A.Chess Placing
题意：给了一维的一个棋盘，共有n（n必为偶数）个格子。棋盘上是黑白相间的。现在棋盘上有n/2个棋子，让你全部移动到黑色格子或者白色格子，要求步数最少，并输出步数。
题解：由于黑色或者白色都是固定位置，我们对棋子位置排个序，然后全部移动到任意一个颜色，取两个最小步数的最小值就好了。
#include<bits/stdc++.h>
#define clr(x) memset(x,0,sizeof(x))
#define clr_1(x) memset(x,-1,sizeof(x))
#define mod 1000000007
#define INF 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pbk pop_back
#define ls(i) (i<<1)
#define rs(i) (i<<1|1)
#define mp make_pair
using namespace std;
const int N=1e5+;
int a[N],p[N];
int n,d,ans1,ans2;
int main()
{
scanf("%d",&n);
ans1=ans2=;
n/=;
for(int i=;i<=n;i++)
scanf("%d",p+i);
sort(p+,p+n+);
for(int i=;i<=n;i++)
{
ans1+=abs(p[i]-i*);
ans2+=abs(p[i]-(i*-));
}
printf("%d\n",min(ans1,ans2));
return ;
}
B.Switches and Lamps
题意：有n个开关和m盏灯，每个开关都关联一些灯，按下该开关后这些关联的灯如果亮着就保持不变，关着就会亮起。问你存不存在n-1个开关的组合，使得按下这n-1个开关后，所有灯全部亮起。
题解：用0和1标记按下开关i后第j个灯是否亮起。然后求每个灯关联的开关数。接着遍历所有开关。如果存在一组开关，使得他对每个灯的亮起标记数全部小于每个灯的关联开关数，则存在这样一个组合，这个组合是除他以外的其他所有开关。
#include<bits/stdc++.h>
#define clr(x) memset(x,0,sizeof(x))
#define clr_1(x) memset(x,-1,sizeof(x))
#define mod 1000000007
#define INF 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pbk pop_back
#define ls(i) (i<<1)
#define rs(i) (i<<1|1)
#define mp make_pair
using namespace std;
const int N=2e3+;
int a[N],b[N],n,m;
string s[N];
bool flag;
int main()
{
ios::sync_with_stdio(false);
cin.tie();
cout.tie();
cin>>n>>m;
for(int i=;i<=n;i++)
{
cin>>s[i];
for(int j=;j<m;j++)
{
if(s[i][j]=='')
a[j+]++;
}
}
for(int i=;i<=n;i++)
{
clr(b);
flag=;
for(int j=;j<m;j++)
if(s[i][j]=='')
b[j+]++;
for(int j=;j<=m;j++)
if(b[j]==a[j])
{
flag=;
break;
}
if(flag==)
return !printf("YES\n");
}
return !printf("NO\n");
}
C.Liebig's Barrels
题意：给你n*k块木板，要你做n个桶，每个桶由k块木板组成。每个桶的盛水量由最短的木板决定。让你最大化这n个木桶的总盛水量，并且每每对木桶的盛水量差不超过l。
题解：给所有板从小到大排个序，然后看最短板往上n块板是不是都小于等于其长度+l，如果不满足则做不出这样的桶组合。现在我们取n块板来造这n个木桶，作为每个桶的最短板。先算其长度+l的木板所在的位置t，然后从第一块最短板开始，每隔k个取一块板，直到板位置超过了t。然后从t位置往前取，除了前面取过的位置，一个一个地取板。按照上述操作取板，直到取了n块板作为木桶的最短板。这时候盛水量就为这n块板长度和。
#include<bits/stdc++.h>
#define clr(x) memset(x,0,sizeof(x))
#define clr_1(x) memset(x,-1,sizeof(x))
#define mod 1000000007
#define INF 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pbk pop_back
#define ls(i) (i<<1)
#define rs(i) (i<<1|1)
#define mp make_pair
using namespace std;
const int N=1e5+;
int a[N],b[N],n,m,k,l,t,pp;
LL ans;
int main()
{
ios::sync_with_stdio(false);
cin.tie();
cout.tie();
cin>>n>>k>>l;
m=n*k;
for(int i=;i<=m;i++)
cin>>a[i];
sort(a+,a+m+);
if(a[n]-a[]>l)
{
cout<<<<endl;
return ;
}
t=upper_bound(a+,a+m+,a[]+l)-a;
ans=;
t--;
pp=;
for(int i=;i<=t && pp<n;i+=k)
ans+=1LL*a[i],pp++;
for(int i=t;i>= && pp<n;i--)
{
if(i%k==)
continue;
else
ans+=1LL*a[i],pp++;
}
printf("%I64d\n",ans);
return ;
}
D.Sand Fortress
题意：给你无穷个点，从左到右为0,1,2,3…+∞。然后给你n块积木往点上放，要求所有相邻两个点间的积木高度差不超过1。并且约束第一堆积木的高度最大值。问你把这n块积木分配到这些点上后，有放积木的点的数量最少为多少？
题解：如果要求第一堆积木数量最大为1，我们可以想象我们如果要放积木到k堆上积木数最大的情况是形成一个小山一样的，相邻堆差为1的情况。那现在我们约束了第一堆最大高度为h，我们要造k堆。那么积木数最大时，我们第一堆右侧的情况，就是(k+h-1)这个小山中第k堆（包含第k堆）左侧的小山翻转过来的样子。那么我们要求更小的积木数时，就可以通过从上到下拿走积木构成，因此k堆的可达成的积木数是0~这个最大值。对于本题，我们二分查找构成的堆数，用上述方法判断该堆能不能放n个积木，来找到堆数最小值。
此题还需要一点高精度。
#include<bits/stdc++.h>
#define clr(x) memset(x,0,sizeof(x))
#define clr_1(x) memset(x,-1,sizeof(x))
#define mod 100000000
#define LL long long
#define pb push_back
#define pbk pop_back
#define ls(i) (i<<1)
#define rs(i) (i<<1|1)
#define mp make_pair
using namespace std;
LL n,h,lt,rt;
LL mid;
LL t[],k[];
void mul(LL *a,LL p)
{
LL g[],ans[];
clr(g);
clr(ans);
g[]=p%mod;
p/=mod;
g[]=p%mod;
p/=mod;
g[]=p%mod;
for(int i=;i<;i++)
{
for(int j=;j<;j++)
ans[i+j]+=g[j]*a[i];
}
for(int i=;i<;i++)
ans[i+]+=ans[i]/mod,ans[i]%=mod;
for(int i=;i<;i++)
a[i]=ans[i];
return ;
}
void add(LL *a,LL p)
{
LL g[];
clr(g);
g[]=p%mod;
p/=mod;
g[]=p%mod;
p/=mod;
g[]=p%mod;
for(int i=;i<;i++)
a[i]=a[i]+g[i];
for(int i=;i<;i++)
a[i+]+=a[i]/mod,a[i]%=mod;
return ;
}
void sub(LL *a,LL *b)
{
for(int i=;i<;i++)
{
a[i]-=b[i];
if(a[i]<)
a[i]+=mod,a[i+]--;
}
return ;
}
bool cmp(LL *a,LL p)
{
LL g[];
clr(g);
g[]=p%mod;
p/=mod;
g[]=p%mod;
p/=mod;
g[]=p%mod;
for(int i=;i>=;i--)
if(a[i]>g[i]) return true;
else if(a[i]<g[i]) return false;
return true;
}
int main()
{
scanf("%I64d%I64d",&n,&h);
lt=;
rt=n;
while(rt-lt>)
{
clr(t);
t[]=;
mid=lt+rt>>;
if(mid<=h)
mul(t,((mid+)%==?(mid+)/:(mid+))),mul(t,mid%==?mid/:mid);
else
{
if((mid+h-)&)
mul(t,(mid+h-)/),mul(t,(mid+h+)/),add(t,(mid+h-)/+);
else
mul(t,(mid+h-)/),mul(t,(mid+h+)/);
clr(k);
k[]=;
mul(k,h%==?h/:h);
mul(k,(h-)%==?(h-)/:(h-));
sub(t,k);
}
if(cmp(t,n))
rt=mid;
else
lt=mid;
}
printf("%I64d\n",rt);
return ;
}
E.Pencils and Boxes
题意：给你n个数字，让你把他们随意分配到任意数量的集合里，要求集合内数字的个数不小于k，并且任意两个数字之差不大于d。问是否能找到这样的一种集合构造。
题解：我们仍旧把数字排个序，可知每个集合包含排序后的一段连续数字。然后从后往前dp，dp他是不是能成为某个集合左端点（最小数字）。如果该数字为集合左端点，则该位置标记1，否则标记0。处理到第i个数字时，我们lower_bound出他的值+d的数字位置t，然后看看[i+k,t+1]位置有没有左端点，如果有，那么该位置也能成为左端点，标记1。由于这个区间可能很大，我们写个最大值线段树来查询这个位置区间。最后如果1能成为左端点，那么说明存在这样的集合构造，否则不存在。
#include<bits/stdc++.h>
#define clr(x) memset(x,0,sizeof(x))
#define clr_1(x) memset(x,-1,sizeof(x))
#define mod 1000000007
#define INF 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pbk pop_back
#define ls(i) (i<<1)
#define rs(i) (i<<1|1)
#define mp make_pair
using namespace std;
const int N=5e5+;
int n,k,d;
int a[N];
struct node
{
int l,r,maxn;
}tree[N<<];
void init(int i,int l,int r)
{
tree[i]=(node){l,r,};
if(l==r) return ;
int mid=l+r>>;
init(ls(i),l,mid);
init(rs(i),mid+,r);
return ;
}
void upd(int i,int pos,int val)
{
if(tree[i].l==tree[i].r) {tree[i].maxn=val; return ; }
int mid=tree[i].l+tree[i].r>>;
if(mid>=pos) upd(ls(i),pos,val);
else upd(rs(i),pos,val);
tree[i].maxn=max(tree[ls(i)].maxn,tree[rs(i)].maxn);
return ;
}
int qy(int i,int l,int r)
{
if(tree[i].l>=l && tree[i].r<=r) return tree[i].maxn;
int mid=tree[i].l+tree[i].r>>;
int ans=;
if(l<=mid) ans=max(ans,qy(ls(i),l,r));
if(r>mid) ans=max(ans,qy(rs(i),l,r));
return ans;
}
int main()
{
scanf("%d%d%d",&n,&k,&d);
for(int i=;i<=n;i++)
scanf("%d",a+i);
sort(a+,a+n+);
init(,,n);
for(int i=n-k+;i>=;i--)
{
int t=upper_bound(a+,a+n+,a[i]+d)-a;
t--;
if(t==n) {upd(,i,); continue;}
if(i+k>t+) continue;
upd(,i,qy(,i+k,t+));
}
if(qy(,,)==) printf("YES\n");
else printf("NO\n");
return ;
}
F.Isomorphic Strings
题意：给你一个字符串s，然后q个询问。每个询问给出两个该串的子串（长度相同），问能否对每个字母找到一个双射f(x)，使得子串1能够通过双射f(x)变成子串2，子串2能通过f(x)反函数f'(x)变为子串1。
题解:我们把26个字母拆开来，如果该位置有该字母则标1，否则标0，对该字符串做26个字母的双hash。然后询问时，我们对每个询问子串h1，看其内所有出现过的字母在h2里有没有一样的标记序列（hash值）。如果都有那么说明存在这样的双射。如果其中有一个没有那么则不存在。
为什么双hash？ 因为有个大佬造了一组数据卡单hash里的ull情况orz。真的是很强。
#include<bits/stdc++.h>
#define clr(x) memset(x,0,sizeof(x))
#define clr_1(x) memset(x,-1,sizeof(x))
#define LL long long
#define pb push_back
#define pbk pop_back
#define ls(i) (i<<1)
#define rs(i) (i<<1|1)
#define mp make_pair
using namespace std;
const int N=2e5+;
const int maxn=2e5;
const LL mod[]={,};
LL bit[N][];
LL rk[N][][],num[N][];
int n,m,t,h1,h2,len;
char s[N];
bool flag,rflag;
int main()
{
bit[][]=bit[][]=;
for(int i=;i<=maxn;i++)
for(int j=;j<;j++)
bit[i][j]=(bit[i-][j]<<)%mod[j];
scanf("%d%d",&n,&m);
scanf("%s",s+);
for(int i=;s[i];i++)
{
t=s[i]-'a';
for(int j=;j<;j++)
{
for(int k=;k<;k++)
if(t==j)
rk[i][j][k]=(rk[i-][j][k]<<|)%mod[k];
else
rk[i][j][k]=(rk[i-][j][k]<<)%mod[k];
if(t==j)
num[i][j]=num[i-][j]+;
else
num[i][j]=num[i-][j];
}
}
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&h1,&h2,&len);
rflag=;
for(int j=;j<;j++)
if(num[h1+len-][j]>num[h1-][j])
{
flag=;
for(int k=;k<;k++)
{
if(((rk[h1+len-][j][]-rk[h1-][j][]*bit[len][]%mod[])%mod[]+mod[])%mod[]==((rk[h2+len-][k][]-rk[h2-][k][]*bit[len][]%mod[])%mod[]+mod[])%mod[] && ((rk[h1+len-][j][]-rk[h1-][j][]*bit[len][]%mod[])%mod[]+mod[])%mod[]==((rk[h2+len-][k][]-rk[h2-][k][]*bit[len][]%mod[])%mod[]+mod[])%mod[] )
{
flag=;
break;
}
}
if(flag==)
{
rflag=;
break;
}
}
if(rflag)
printf("YES\n");
else
printf("NO\n");
}
return ;
}
G.Team Players
题意：给出数字0~(n-1)，并给出m个数字对，要求你找出所有的三元组(a,b,c),a<b<c，并且其中不能包含这些数字对。然后让你输出所有三元组A*a+B*b+C*c的和。
题解：我们用容斥定理，把所有三元组和求出来，减去包含至少包含其中一个数字对的三元组的和，加上至少包含其中两个数字对的三元组的和，减掉包含其中三个数字对的三元组的和。最后一个情况要找三元环，通过了大佬的写法才知道怎么有技巧的暴力查找这样的三元环orz。
由于要mod 2^64，直接用ull去做就好了。
#include<bits/stdc++.h>
#define clr(x) memset(x,0,sizeof(x))
#define clr_1(x) memset(x,-1,sizeof(x))
#define mod 1000000007
#define INF 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pbk pop_back
#define ls(i) (i<<1)
#define rs(i) (i<<1|1)
#define mp make_pair
#define ull unsigned long long
#define fi first
#define se second
using namespace std;
const int N=2e5+;
ull a,b,c,ans;
vector<int> e[N];
vector<pair<int,int> > pe;
vector<int> g[N];
int n,m,k,t,u,v,r,d;
int sz[N];
ull calc(int p0,int p1,int p2)
{
int st[]={p0,p1,p2};
sort(st,st+);
return a*st[]+b*st[]+c*st[];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie();
cout.tie();
cin>>n>>m;
cin>>a>>b>>c;
ans=;
for(int i=;i<n;i++)
{
ans+=a*i*((ull)(n--i)*(n--i)/);
ans+=b*i*i*(n--i);
ans+=c*i*((ull)i*(i-)/);
}
pe.pb(mp(,));
for(int i=;i<=m;i++)
{
cin>>u>>v;
e[u].pb(v);
e[v].pb(u);
pe.pb(mp(u,v));
if(u>v) swap(u,v);
ans-=(a*u+b*v)*(n--v)+c*((ull)(v+n)*(n--v)/);
ans-=(a*u+c*v)*(v-u-)+b*((ull)(u+v)*(v-u-)/);
ans-=(b*u+c*v)*u+a*((ull)(u-)*u/);
}
for(int i=;i<n;i++)
{
r=;
sz[i]=e[i].size();
sort(e[i].begin(),e[i].end());
for(int j=;j<sz[i];j++)
{
d=e[i][j];
if(d<i)
ans+=a*d*(sz[i]--j)+b*d*j,r++;
else
ans+=b*d*(sz[i]--j)+c*d*j;
}
ans+=a*i*((ull)(sz[i]-r)*(sz[i]-r-)/)+b*i*r*(sz[i]-r)+c*i*((ull)r*(r-)/);
}
for(int i=;i<=m;i++)
{
u=pe[i].fi;
v=pe[i].se;
if(sz[u]>sz[v] || (sz[u]==sz[v] && u>v)) swap(u,v);
g[u].pb(v);
}
for(int i=;i<n;i++)
sort(g[i].begin(),g[i].end());
for(int i=;i<=m;i++)
{
u=pe[i].fi;
v=pe[i].se;
auto p0=g[u].begin();
auto p1=g[v].begin();
while(p0!=g[u].end() && p1!=g[v].end())
if(*p0==*p1) ans-=calc(u,v,*p0),p0++,p1++;
else if(*p0<*p1) p0++;
else p1++;
}
cout<<ans<<endl;
return ;
}