2016 ACM / ICPC Asia Regional Qingdao Online

2016年10月8日7,7771

大部分都是队友写的代码QAQ

我主要是填坑个题解

1001 I Count Two Three

定义『I Count Two Three Number』为\(2^a3^b5^c7^d\)

问超过n的最小的这种数字

显然这样的数字数量是很少的，其质因数个数不会超过30个

dfs出所有数字，二分查询

1002 Cure

求\(\sum\limits_{k=1}^n \frac{1}{k^2}\)

\(\lim_{n \rightarrow \infty}\) \(\sum\limits_{k=1}^n \frac{1}{k^2}=\frac{\pi^2}{6}\)

n超过十几万之后就达到精度上限

1003 Family View

把一个文本串的所有匹配模式串的子串变为’*’

AC自动机模板

1004 Tea

给定一个装有体积为[L,R]的茶壶，给两个杯子

每次操作可以往茶杯中倒定量的茶，返回操作是否成功

要求最终两个茶杯的茶体积差小于1，茶壶剩余的茶小于1

问至少需要多少步，能处理体积区间内的任一情况

把边界情况特判完后，一边放L/2+0.5，一边放L/2+1.5

然后每次倒 2

1005 Balanced Game

问n种手势的『石头剪刀布』游戏是否存在公平的玩法

每种手势与其它手势有n-1种关系

如果n-1是奇数，就不存在公平玩法，否则可以构造出公平的玩法

1006 The Best Path

给定一张无向图，求一条欧拉路，使得路上所有点权异或和最大

奇度点为0或2存在欧拉路，每个结点贡献可以由度数算出，如果没有奇度点的话，就枚举起点

1007 Sort

给定n个数，每次将其中k个合并，代价为他们的和，并将和放入队列，最后合并为一个数，要求总代价不超过T，求最小的K值

答案满足二分性质，K叉哈夫曼树

1008 Tower Defence

给定一棵边权树，随机删一条边，求两条直径中较大一条的期望

先dfs出原树直径，并从直径两端分别做一次dp，预处理以其为根时所有子树的直径

如果删掉的边与直径无交，直径不变

否则把求所有切出来的子树的最大直径

1010 Herbs Gathering

n个物品，每个物品有体积和价值，问总体积不超过m的最大价值。

注意到m，t，v纯随机，那么不会选太多的草药,而耗时较少的草药有很大概率存在于最优解中

用这些性质优化搜索

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<cmath>
#define ll long long
#define inf 1000000000
using namespace std;
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;
}
int n,m;
ll ans;
ll sw[105],sv[105];
struct data{
    int w,val; 
}a[105];
bool operator<(data a,data b)
{
    return a.w>b.w;
}
void dfs(int x,ll sumw,ll sumv)
{
    ans=max(ans,sumv);
    if(sumw+a[n].w>m)return;
    if(sumv+sv[x]<ans)return;
    if(sumw+sw[x]<=m)
    {
        ans=max(ans,sumv+sv[x]);
        return;
    }
    if(sumw+a[x].w<m)
        dfs(x+1,sumw+a[x].w,sumv+a[x].val);
    dfs(x+1,sumw,sumv);
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        ans=0;
        for(int i=1;i<=n;i++)
            a[i].w=read(),a[i].val=read();
        sort(a+1,a+n+1);
        sw[n+1]=sv[n+1]=0;
        for(int i=n;i>=1;i--)
        {
            sw[i]=sw[i+1]+a[i].w;
            sv[i]=sv[i+1]+a[i].val;
        }
        dfs(1,0,0);
        cout<<ans<<endl;
    }
    return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<queue>

#include<cmath>

#define ll long long

#define inf 1000000000

using namespace std;

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;

}

int n,m;

ll ans;

ll sw[105],sv[105];

struct data{

int w,val;

}a[105];

bool operator<(data a,data b)

{

return a.w>b.w;

}

void dfs(int x,ll sumw,ll sumv)

{

ans=max(ans,sumv);

if(sumw+a[n].w>m)return;

if(sumv+sv[x]<ans)return;

if(sumw+sw[x]<=m)

{

ans=max(ans,sumv+sv[x]);

return;

}

if(sumw+a[x].w<m)

dfs(x+1,sumw+a[x].w,sumv+a[x].val);

dfs(x+1,sumw,sumv);

}

int main()

{

while(scanf("%d%d",&n,&m)!=EOF)

{

ans=0;

for(int i=1;i<=n;i++)

a[i].w=read(),a[i].val=read();

sort(a+1,a+n+1);

sw[n+1]=sv[n+1]=0;

for(int i=n;i>=1;i--)

{

sw[i]=sw[i+1]+a[i].w;

sv[i]=sv[i+1]+a[i].val;

}

dfs(1,0,0);

cout<<ans<<endl;

}

return 0;

}

1011 Barricade

无向图，要求选择最少的边，使得1到n的最短路一定经过其中的边

求最短路图的最小割，模板题

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<cmath>
#define inf 1000000000
using namespace std;
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;
}
int T,test,cnt;
int n,m,last[1005],q[1005],h[1005],dis[1005];
int u[10005],v[10005],w[10005];
vector<int>to[1005];
struct edge{
    int to,next,v;
}e[100005];
void insert(int u,int v,int w)
{
    e[++cnt]=(edge){v,last[u],w};last[u]=cnt;
    e[++cnt]=(edge){u,last[v],0};last[v]=cnt;
}
void getdis()
{
    int head=0,tail=1;
    for(int i=1;i<=T;i++)dis[i]=-1;
    dis[1]=0;q[0]=1;
    while(head!=tail)
    {
        int x=q[head];head++;
        for(int i=0;i<to[x].size();i++)
            if(dis[to[x][i]]==-1)
            {
                dis[to[x][i]]=dis[x]+1;
                q[tail++]=to[x][i];
            }
    }
}
bool bfs()
{
    int head=0,tail=1;
    for(int i=1;i<=T;i++)h[i]=-1;
    q[0]=1;h[1]=0;
    while(head!=tail)
    {
        int x=q[head];head++;
        for(int i=last[x];i;i=e[i].next)
            if(e[i].v&&h[e[i].to]==-1)
            {
                h[e[i].to]=h[x]+1;
                q[tail++]=e[i].to;
            }
    }
    return h[T]!=-1;
}
int dfs(int x,int f)
{
    if(x==T)return f;
    int w,used=0;
    for(int i=last[x];i;i=e[i].next)
        if(h[e[i].to]==h[x]+1)
        {
            w=dfs(e[i].to,min(e[i].v,f-used));
            e[i].v-=w;e[i^1].v+=w;
            used+=w;if(used==f)return f;
        }
    if(!used)h[x]=-1;
    return used;
}
int dinic()
{
    int ans=0;
    while(bfs())ans+=dfs(1,inf);
    return ans;
}
int main()
{
    test=read();
    while(test--)
    {
        n=read();m=read();
        T=n;cnt=1;
        for(int i=1;i<=n;i++)
            to[i].clear();
        memset(last,0,sizeof(last));
        for(int i=1;i<=m;i++)
        {
            u[i]=read(),v[i]=read(),w[i]=read();
            to[u[i]].push_back(v[i]);
            to[v[i]].push_back(u[i]);
        }
        getdis();
        for(int i=1;i<=m;i++)
            if(dis[u[i]]+1==dis[v[i]])
                insert(u[i],v[i],w[i]);
            else if(dis[v[i]]+1==dis[u[i]])
                insert(v[i],u[i],w[i]);
        printf("%d\n",dinic());
    }
    return 0;   
}

100

101

102

103

104

105

106

107

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<queue>

#include<cmath>

#define inf 1000000000

using namespace std;

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;

}

int T,test,cnt;

int n,m,last[1005],q[1005],h[1005],dis[1005];

int u[10005],v[10005],w[10005];

vector<int>to[1005];

struct edge{

int to,next,v;

}e[100005];

void insert(int u,int v,int w)

{

e[++cnt]=(edge){v,last[u],w};last[u]=cnt;

e[++cnt]=(edge){u,last[v],0};last[v]=cnt;

}

void getdis()

{

int head=0,tail=1;

for(int i=1;i<=T;i++)dis[i]=-1;

dis[1]=0;q[0]=1;

while(head!=tail)

{

int x=q[head];head++;

for(int i=0;i<to[x].size();i++)

if(dis[to[x][i]]==-1)

{

dis[to[x][i]]=dis[x]+1;

q[tail++]=to[x][i];

}

bool bfs()

{

int head=0,tail=1;

for(int i=1;i<=T;i++)h[i]=-1;

q[0]=1;h[1]=0;

while(head!=tail)

{

int x=q[head];head++;

for(int i=last[x];i;i=e[i].next)

if(e[i].v&&h[e[i].to]==-1)

{

h[e[i].to]=h[x]+1;

q[tail++]=e[i].to;

}

return h[T]!=-1;

}

int dfs(int x,int f)

{

if(x==T)return f;

int w,used=0;

for(int i=last[x];i;i=e[i].next)

if(h[e[i].to]==h[x]+1)

{

w=dfs(e[i].to,min(e[i].v,f-used));

e[i].v-=w;e[i^1].v+=w;

used+=w;if(used==f)return f;

}

if(!used)h[x]=-1;

return used;

}

int dinic()

{

int ans=0;

while(bfs())ans+=dfs(1,inf);

return ans;

}

int main()

{

test=read();

while(test--)

{

n=read();m=read();

T=n;cnt=1;

for(int i=1;i<=n;i++)

to[i].clear();

memset(last,0,sizeof(last));

for(int i=1;i<=m;i++)

{

u[i]=read(),v[i]=read(),w[i]=read();

to[u[i]].push_back(v[i]);

to[v[i]].push_back(u[i]);

}

getdis();

for(int i=1;i<=m;i++)

if(dis[u[i]]+1==dis[v[i]])

insert(u[i],v[i],w[i]);

else if(dis[v[i]]+1==dis[u[i]])

insert(v[i],u[i],w[i]);

printf("%d\n",dinic());

}

return 0;

}

1012 Eighty seven

给定一些数字，每次询问删去其中的某三个数，剩下的数能不能选出10个凑成87

先求一组解，询问和解没交直接输出Yes，bitset优化背包预处理其它询问的答案

« 「CF715X」Codeforces Round #372 (Div. 1) 2016 CCPC Changchun Onsite »

钟子谦

你们怎么都能过1003…这题不是卡空间吗

hzwer.com _ Home | http://hzwer.com