PieOrDolphin
Topcoder SRM617-Div1-Lv2
题意
有 \(n\ (\leq50)\) 个人，给他们发礼物，共有 \(m\ (\leq1000)\) 天，每天要给两个人发礼物，其中一个人获得一号礼物，另一个获得二号礼物，定义一个方案的总和为每个人获得的一号二号礼物数之差的和。现在每一天要发礼物的两个人已经确定，但是你可以选择给谁发一号或二号礼物，构造方案使得总和最小。
思路
将每一天的礼物方案抽象为一条边，获得一号礼物的人向获得二号礼物的人连一条有向边，因此每个人的出度即为获得一号礼物数，入度同理为二号礼物数，那么我们的目标即为通过确定每一条边的方向来最小化每个点入度出度之差。直接遍历并直接确定方向十分困难，我们考虑不断贪心反转边来寻找更优的答案，具体来说，考虑到对于一条简单路径，如果反转路径上所有边，那么路径上除了首尾端点的其他点不会受到影响（原先的一个出度变为入度，原先的一个入度变为出度），而首端点则出度 \(-1\)，入度 \(+1\)，尾端点反之。因此，我们每次找到出入度之差 \(\geq2\) 的点 \(st\)，以 \(outd[i]-ind[i]\geq 2\) 的情况为例，我们再找到另外一个 \(ind[i]-outd[i]\geq 1\)[1] 的点 \(ed\)，将 \(st\) 到 \(ed\) 简单路径的全部边反转即可，为了方便处理，对于 \(ind[i]-outd[i]\geq 2\) 的情况，直接将整张图反转，再用相同方法处理。
代码
#include<bits/stdc++.h>
using namespace std;
#ifdef ONLINE_JUDGE
#define getchar __getchar
inline char __getchar(){
static char ch[1<<20],*l,*r;
return (l==r&&(r=(l=ch)+fread(ch,1,1<<20,stdin),l==r))?EOF:*l++;
}
#endif
template<class T>inline void rd(T &x){
T res=0,f=1;
char ch=getchar();
while(ch<'0' || ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while('0'<=ch && ch<='9'){res=res*10+ch-'0';ch=getchar();}
x=res*f;
}
template<class T>inline void wt(T x,char endch='\0'){
static char wtbuff[20];
static int wtptr;
if(x==0){
putchar('0');
}
else{
if(x<0){x=-x;putchar('-');}
wtptr=0;
while(x){wtbuff[wtptr++]=x%10+'0';x/=10;}
while(wtptr--) putchar(wtbuff[wtptr]);
}
if(endch!='\0') putchar(endch);
}
const int MAXN=1e3+5,MAXM=55;
typedef pair<int,int> pii;
int n,ans[MAXN],ind[MAXM],oud[MAXM];//ans[i]=1正向，2逆向
pii gift[MAXN];
inline void solve(){
int st,ed,cur;
pii pre[MAXM];
while(1){
st=-1;ed=-1;
for(int i=0;i<50;i++){
if(abs(ind[i]-oud[i])>=2){
st=i;break;
}
}
if(st==-1) return;
if (ind[st]>oud[st]){
for(int i=1;i<=n;i++) ans[i]=3-ans[i];
for (int i=0;i<50;i++) swap(ind[i],oud[i]);
}
fill(pre,pre+50,make_pair(-1,-1));
queue<int>q;q.push(st);
while(!q.empty()){
cur=q.front();q.pop();
if(ind[cur]>oud[cur]){
ed=cur;break;
}
for(int i=1,u,v;i<=n;i++){
u=gift[i].first;v=gift[i].second;
if(ans[i]==2) swap(u,v);
if(u==cur && v!=st){
if(pre[v].first==-1){
pre[v]=make_pair(u,i);
q.push(v);
}
}
}
}
cur=ed;
int nxt;
while(pre[cur].first!=-1){
nxt=pre[cur].first;
ans[pre[cur].second]=3-ans[pre[cur].second];
ind[cur]--;
oud[cur]++;
ind[nxt]++;
oud[nxt]--;
cur=nxt;
}
}
}
int main(){
rd(n);
for(int i=1;i<=n;i++){
rd(gift[i].first);
oud[gift[i].first]++;
}
rd(n);
for(int i=1;i<=n;i++){
rd(gift[i].second);
ind[gift[i].second]++;
}
fill(ans+1,ans+1+n,1);
solve();
for(int i=1;i<=n;i++){
wt(ans[i],' ');
}
// int cnt=0;
// for(int i=0;i<50;i++){
// cnt+=abs(ind[i]-oud[i]);
// }
// cout<<cnt<<endl;
return 0;
}
CtuRobots
Topcoder SRM647-Div1-Lv2
题意
有 \(n\ (\leq 500)\) 个机器人，每个机器人的价格为 \(cost_i\ (\leq 10^4)\)，油箱容量为 \(cap_i\ (\leq 10^9)\)，一单位燃料可以走一单位距离，你可以给购买的机器人编号，机器人 \(k\) 可以给机器人 \(k+1\) 补充燃料，但是任意时刻机器人的燃料不能超过其油箱容量上限，你有 \(B\ (\leq 10^4)\) 的预算，购买一些机器人，机器人从 \(0\) 出发，问所有机器人最终都能返回初始点的前提下，能探索到的最大距离。
思路
Tips: 题目并没有对于“速度”进行规定，也就是说，只要距离限制满足，可以视为一台机器人可以在任何时刻到某个地方，不过这个性质并不影响做题
子问题 1
假设我们已经知道了所有已经购买的机器人，如何计算能够探索的最大距离？一个显然的思路是我们只需要油箱最大的机器人进行探索任务，而其他的机器人的任务只是给它补充燃料，两个机器人同时执行探索任务只会浪费燃料没有任何好处。并且我们可以发现，对于某台负责补充燃料的机器人 \(i\)，它的最佳选择是在 \(\large\frac{cap_i}{3}\) 处给下一个机器人提供燃料并返航，因为如果小于这个节点时可提供的燃料大于可被接收的燃料造成浪费，而大于这个节点自己会消耗额外的燃料。而且一个很巧妙的性质在于在 \(\large\frac{cap_i}{3}\) 处给下一个机器人补充燃料后，下一个机器人刚好回满。因此我们只需要将机器人的油箱容量从小到大排序，设 \(f_i\) 为机器人 \(i\) 的实际续航时间，有递推关系：\(\large f_1=cap_1,f_2=\frac{f_1}{3}+cap_2,\dots,f_i=\frac{f_{i-1}}{3}+cap_i\)，而能探索到的最大距离便为油箱最大的机器人 \(k\) 的续航除以 \(2\) 即 \(\large\frac{f_k}{2}\)。
子问题 2
如何购买机器人使得探索距离最大？我们对于刚才的递推关系再加上预算的限制，就可以 DP 了，首先将机器人按油箱大小排序，设 \(f[i][j]\) 表示前 \(i\) 个机器人可选，预算为 \(j\) 时最大可能的续航（由于还要返程所以答案为 \(f[i][j]/2\)），每次的决策为判断是否购买第 \(i\) 个机器人。
代码
#include<bits/stdc++.h>
#define getmax(x,y) x=max(x,y)
using namespace std;
#ifdef ONLINE_JUDGE
#define getchar __getchar
inline char __getchar(){
static char ch[1<<20],*l,*r;
return (l==r&&(r=(l=ch)+fread(ch,1,1<<20,stdin),l==r))?EOF:*l++;
}
#endif
template<class T>inline void rd(T &x){
T res=0,f=1;
char ch=getchar();
while(ch<'0' || ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while('0'<=ch && ch<='9'){res=res*10+ch-'0';ch=getchar();}
x=res*f;
}
typedef double db;
const db eps=1e-8;
const int MAXN=505,MAXB=1e4+5;
int n,bud;
db f[MAXN][MAXB];
struct BOT{
int cost;
db cap;
bool operator < (const BOT& b){
return cap<b.cap;
}
}bt[MAXN];
int main(){
rd(bud);
rd(n);
for(int i=1;i<=n;i++){
rd(bt[i].cost);
}
rd(n);
for(int i=1;i<=n;i++){
rd(bt[i].cap);
}
sort(bt+1,bt+1+n);
for(int i=1;i<=n;i++){
memcpy(f[i],f[i-1],sizeof(f[i]));
for(int j=bt[i].cost;j<=bud;j++){
getmax(f[i][j],f[i-1][j-bt[i].cost]/3+bt[i].cap);
}
}
cout<<fixed<<setprecision(8)<<f[n][bud]/2.0<<endl;
return 0;
}
PathGame
Topcoder SRM637-Div1-Lv2
题意
\(2\) 行若干列的方格图，格子为黑色\((\#)\)或白色\((.)\)，Snuke 与 Sothe 轮流在上面把白格涂黑，如果有一条从左到右的白色路径，游戏继续，否则游戏结束且最后涂色的玩家判输，保证初始有路径，双方皆用最优策略，判断最后胜者。
思路
我们记录 \(f[l][r][i]\) 为长度为 \(i\) 的全白格的 \(SG\) 函数，\(l,r\) 分别表示左右端只能从上方出发\((0)\)，只能从下方出发\((1)\)，上下均可出发\((2)\)，列举长度为 \(1\) 时最基本的情况赋初值，枚举长度，再枚举中间的断点（涂黑的块）进行转移，显然中间涂黑块所在列 \(SG\) 函数为 \(0\)，而左右两边的子块已在长度更小的情况下处理过，因此根据 \(SG\) 定理异或在一起即可。最后将原方格图根据黑格分段，求亦或和即可。
代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int n,f[3][3][MAXN];
string s[3];
bitset<MAXN>ava;
int main(){
cin>>n>>s[1]>>s[2];
n=s[1].size();
f[0][1][1]=0;
f[1][0][1]=0;
f[0][0][1]=1;
f[2][0][1]=1;
f[2][1][1]=1;
f[0][2][1]=1;
f[1][2][1]=1;
f[1][1][1]=1;
f[2][2][1]=1;
for(int i=2;i<=n;i++){
for(int l=0;l<=2;l++){
for(int r=0;r<=2;r++){
ava.reset();
for(int j=0;j<i;j++){
if(!((j==0&&l==1)||(j==i-1&&r==1))) ava[f[l][0][j]^f[0][r][i-j-1]]=1;
if(!((j==0&&l==0)||(j==i-1&&r==0))) ava[f[l][1][j]^f[1][r][i-j-1]]=1;
}
for(int j=0;j<=n;j++){
if(!ava[j]){
f[l][r][i]=j;
break;
}
}
}
}
}
int ans=0,lasti=-1,lastdir=2;
for(int i=0;i<n;i++){
if(s[1][i]=='#') ans^=f[lastdir][1][i-lasti-1],lasti=i,lastdir=1;
else if(s[2][i]=='#') ans^=f[lastdir][0][i-lasti-1],lasti=i,lastdir=0;
}
ans^=f[lastdir][2][n-lasti-1];
if(ans!=0) puts("Snuke");
else puts("Sothe");
return 0;
}
为什么尾端点只需要 \(\geq 1\) 即可？因为只要尾端点有差值，反转后最坏情况尾端点无贡献，但是首端点一定有贡献，这样做才能找到所有可能的贡献 ↩︎