「ARC 109A」Hands
Link.
讨论即可，除了煞笔出题人写了个死马的题面。
#include<cstdio>
#include<algorithm>
using namespace std;
int a,b,x,y,ans;
int main()
{
scanf("%d%d%d%d",&a,&b,&x,&y);
if(a>b) printf("%d
",min(x<<1,y)*max(0,abs(a-b)-1)+x);
else printf("%d
",min(x<<1,y)*max(0,abs(a-b))+x);
return 0;
}
「ARC 109B」log
Link.
要贪心的取的话，肯定是先把 (n+1) 取了，然后我们来二分。
(1-n) 分别有 (n+1) 到 (2) 种方法可以组成他。
然后来考虑怎么 check。
可以知晓，如果没有这一块多的木块，就一定需要 (n) 块木头。
然后就按开头那个贪心，把 (n+1) 从 (1) 分完，剩下的再依次分。
#include<cstdio>
unsigned long long n;
bool check(unsigned long long x)
{
return (x*(x+1)>>1)<=n+1;
}
unsigned long long search(unsigned long long l,unsigned long long r)
{
unsigned long long res=0;
while(l<=r)
{
unsigned long long mid=(l+r)>>1;
if(check(mid))
{
l=mid+1;
res=n-mid+1;
}
else r=mid-1;
}
return res;
}
int main()
{
scanf("%llu",&n);
printf("%llu
",search(1,2e9));
return 0;
}
「ARC 109C」Large RPS Tournament
Link.
(2^{k})！好耶！！！
考虑倍增 DP。设 (f_{i,j}) 为区间 ([i,i+2^{j}-1]) 的 winner's hand。
设计一个函数 ( ext{tournament}(P,Q)) 为 (P)、(Q) 比武后的赢家。
转移即
[f_{i,j}= ext{tournament}(f_{i,j-1},f_{i+2^{j-1},j-1})
]
当然你不能直接用 (2^{k}) 当成序列来做，反正他是循环节我们直接做 (k) 轮最后合并即可。
实际实现时不需要这么写（主要是写不来）（好像可以记忆化？）。
#include<string>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
string s;
int n,k;
char tour(char one,char ano)
{
if(one=='R')
{
if(ano=='R') return 'R';
else if(ano=='P') return 'P';
else return 'R';
}
else if(one=='P')
{
if(ano=='R') return 'P';
else if(ano=='P') return 'P';
else return 'S';
}
else
{
if(ano=='R') return 'R';
else if(ano=='P') return 'S';
else return 'S';
}
}
int main()
{
scanf("%d%d",&n,&k);
cin>>s;
while(k--)
{
string tmp=s+s;
for(int i=0;i<n;++i) s[i]=tour(tmp[i<<1],tmp[i<<1|1]);
}
printf("%c
",s[0]);
return 0;
}
「ARC 109D」L
图画出来差不多，向目标进发，步数下界就出来了 (max{|x|,|y|})。
这张图是在这里嫖的：
注意特判一些奇怪的情况，具体自己看代码吧吧吧吧。
#include<cstdio>
#include<algorithm>
using namespace std;
int t,onex,oney,anox,anoy,exx,exy,finalx,finaly;
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d%d%d%d",&onex,&oney,&anox,&anoy,&exx,&exy);
finalx=min(onex,min(anox,exx));
finaly=min(oney,min(anoy,exy));
finalx=(finalx<<1)+(finalx!=onex)+(finalx!=anox)+(finalx!=exx)-1;
finaly=(finaly<<1)+(finaly!=oney)+(finaly!=anoy)+(finaly!=exy)-1;
printf("%d
",max(abs(finalx),abs(finaly))+((finalx==finaly)&&(finalx>1||finalx<0)));
}
return 0;
}
「ARC 109E」1D Reversi Builder
Link.
「ARC 109F」1D Kingdom Builder
Link.