C - Camels and Bridge
题意:一堆骆驼过桥,每个桥有承重和长度,问骆驼从头到尾的最近距离
假设这时候骆驼的过桥顺序已经安排好
每一个桥相当于一个限制条件,限制了[l,r]的最近距离,也就是说,对于每一个骆驼 j,要保证
好了把每个骆驼看作一个节点,跑最长路,NP
最终的图是一个DAG,DP求解最长路
考虑求出来[i,j],因为运用了差分约束的思想,所以不需要让[i,j]严格的表示为这一段的最大长度,只需要令[i,j]表示为承受不住这一段的桥的最大长度就行,可能[i,j]的值比此时求出的值要更大,剩下的交给其他情况处理(因为如果满足了所有的限制条件,这个解一定是一个合法解)
二分处理即可
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{
int l,vmx;
void read(){
scanf("%d%d",&l,&vmx);
}
};
bool cmp(node x,node y){
if(x.l==y.l) return x.vmx>y.vmx;
return x.l<y.l;
}
node mes[100010];
int dis[10],ans=1e18;
int v[10];
int now[10],id[10];
bool use[10];
int a,b,pre[101000],sum[10],dp[10];
void dfs(int gs);
int binary_search(int x);
signed main(){
scanf("%lld%lld",&a,&b);
for(int i=1;i<=a;i++) scanf("%lld",&v[i]);
for(int i=1;i<=b;i++) mes[i].read();
for(int i=1;i<=b;i++){
for(int j=1;j<=a;j++){
if(v[j]>mes[i].vmx){
cout<<-1;
return 0;
}
}
}
sort(mes+1,mes+b+1,cmp);
for(int i=b-1;i>=1;i--) mes[i].vmx=min(mes[i].vmx,mes[i+1].vmx);
dfs(1);
printf("%lld",ans);
return 0;
}
void dfs(int gs){
if(gs>a){
memset(sum,0,sizeof(sum));
for(int i=1;i<=a;i++) sum[i]=sum[i-1]+v[id[i]];
memset(dp,0,sizeof(dp));
for(int i=1;i<=a;i++){
for(int j=1;j<i;j++){
dp[i]=max(dp[i],dp[j]+binary_search(sum[i]-sum[j-1]));
}
}
ans=min(ans,dp[a]);
}
for(int i=1;i<=a;i++){
if(!use[i]){
use[i]=true,id[gs]=i;
dfs(gs+1);
use[i]=false;
}
}
}
int binary_search(int x){
int l=0,r=b;
while(l<r){
int mid=ceil((double)(l+r)/2);
if(mes[mid].vmx>=x) r=mid-1;
else l=mid;
}
return mes[l].l;
}
D - Let's Play Nim
题意:先将n袋金币放到盘子里(每次随意放到任意盘子,盘子无数),再做nim游戏
对于出现偶数次的数量,可以抵消掉,故只需要看出现奇数次数量的
若n是偶数
没有数量出现过奇数次,最后金币异或和一定0,后手赢
否则去掉所有出现偶数次的数量,每次先手选取最大数量的放在一盘,这一盘的总数大于剩余金币的一半,故异或和大于0,先手胜
若n是奇数
先手必胜,就是能够取完一个后后手必胜
取完一个后,n为偶数,后手必胜条件为所有数量都出现偶数次
故先手必胜的条件为仅有一个数量出现了奇数次,否则后手必胜
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
map<int,int>mp;
int t;
int main(){
scanf("%d",&t);
while(t--){
mp.clear();
int a;
scanf("%d",&a);
for(int i=1;i<=a;i++){
int w;
scanf("%d",&w);
mp[w]++;
}
if(a&1){
int cnt=0;
for(auto it=mp.begin();it!=mp.end();it++){
cnt+=((it->second)^1);
}
if(cnt==1) printf("First\n");
else printf("Second\n");
}else{
bool ok=false;
for(auto it=mp.begin();it!=mp.end();it++){
ok=max((int)ok,(it->second)&1);
}
if(!ok) printf("Second\n");
else printf("First\n");
}
}
return 0;
}
E - Keep Graph Disconnected
给定一个图,两个人往里面加边,保证无重边无自环且1,n不连通的情况下加不了边的人输,问谁会输
令最后1的连通块大小为x
故加边条数为 n*(n-1)/2-m-x*(n-x)
若n为奇数,此式奇偶性确定,故结局确定
若n为偶数,此式奇偶性与x有关
令y=n-x
易得每次能够影响x*y奇偶性的连通块大小为奇数
一开始1,n间不能连的边数为x*y
若x与y奇偶性不同,令x奇y偶,因为n为偶数,必然还有奇数块连通块大小为奇数
若先手想要x*y为奇数,将一块奇数大小添加到y上,否则填到x上
然后对方如果用一个奇数块加到x或y上,先手再加到另一块抵消,故先手必胜
若xy奇偶性相同
那么奇数块个数为偶数,此时若已经满足先手要求先手可以一直保持,否则后手可以一直保持(若是后手的要求一定为偶数)
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct dsu{
int fa[100010],sz[100010];
void init(int x){
for(int i=1;i<=x;i++) fa[i]=i,sz[i]=1;
}
int get(int x){
return x==fa[x]?x:fa[x]=get(fa[x]);
}
int get_sz(int x){
return sz[get(x)];
}
void add(int x,int y){
int xx=get(x),yy=get(y);
if(xx!=yy) fa[xx]=yy,sz[yy]+=sz[xx];
}
};
dsu ty;
int t;
signed main(){
scanf("%lld",&t);
while(t--){
int a,b;
scanf("%lld%lld",&a,&b);
ty.init(a);
for(int i=1;i<=b;i++){
int o,k;
scanf("%lld%lld",&o,&k);
ty.add(o,k);
}
int ans=((a*(a-1)/2)&1)^(b&1);
if(!(a&1)){
int c1=0,c2=0;
for(int i=1;i<=a;i++){
c1+=(ty.get(i)==ty.get(1)),c2+=(ty.get(i)==ty.get(a));
}
if((ty.get_sz(1)&1)!=(ty.get_sz(a)&1)) ans=1;
else ans=ans^((ty.get_sz(1)*ty.get_sz(a))&1);
}
ans?printf("First\n"):printf("Second\n");
}
}