2017CCPC Final (哈尔滨)

Time：

Link

分析

ym：czh推了个公式，答案是n-1，没加Case wa了一发，我来背锅了

题意

分析

ym：简单的博弈游戏，大家一起玩一玩就清楚套路了

题意

分析

签到，简单的模拟

题意

分析

题意

给出一些区间，让你选k个区间，使其覆盖的点最多

分析

czh：定义dp[i][j] ：前i个点，选择j个区间的最大值。

#include <iostream>
#include <cstdio>
using namespace std;
#define ll long long

const int maxn = 2005;

int t[maxn],dp[maxn][maxn];
int main()
{
    int T;
    cin>>T;
    for(int cn=1;cn<=T;cn++)
    {
        int ans=0;
        int n,m,k;
        scanf("%d %d %d",&n,&m,&k);
        for(int i=0;i<=n;i++)
        {
            for(int j=0;j<=k;j++)dp[i][j]=0;
            t[i]=0;
        }
        for(int i=1;i<=m;i++)
        {
            int x,y;
            scanf("%d %d",&x,&y);
            for(int j=x;j<=y;j++)
            {
                t[j]=max(t[j],y);
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=k;j++)
            {
                if(t[i])
                    dp[t[i]][j]=max(dp[t[i]][j],dp[i-1][j-1]+t[i]-i+1);
                dp[i][j]=max(dp[i][j],dp[i-1][j]);
            }
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=k;j++)
                ans=max(ans,dp[i][j]);
         cout<<"Case #"<<cn<<": ";
        cout<<ans<<endl;
    }
    return 0;
}

题意

分析

题意

分析

题意

分析

czh：一道简单的差分约束题

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
using namespace std;
const int maxn=2005;
int f[maxn],w[maxn*3],to[maxn*3],nex[maxn*3];
bool vis[maxn];
int out[maxn],cnt=0,dis[maxn],n,m,k;
void add(int a,int b,int c)
{
    cnt++;
    w[cnt]=c;
    to[cnt]=b;
    nex[cnt]=f[a];
    f[a]=cnt;
}
bool spfa()
{
    for(int i=1; i<maxn; i++)dis[i]=-1,vis[i]=0,out[i]=0;
    queue<int>que;
    que.push(1);
    vis[1]=1;
    dis[1]=0;
    while(que.size())
    {
      //  for(int i=1;i<=n;i++)printf(" %d",dis[i]);cout<<endl;
        int x=que.front();
      //  cout<<x<<"out"<<endl;
        vis[x]=0;
        que.pop();
        out[x]++;
        if(out[x]>n)
            return false;
        for(int i=f[x]; i; i=nex[i])
        {
          //  cout<<to[i]<<"to"<<endl;
            if(dis[x]+w[i]>dis[to[i]])
            {
                dis[to[i]]=dis[x]+w[i];
                if(vis[to[i]]==0)
                {
                    que.push(to[i]);
                    vis[to[i]]=1;
                }
            }
        }
    }
    return true;
}
int main()
{
    int T;
    cin>>T;
    for(int cn=1; cn<=T; cn++)
    {
        cnt=0;
        scanf("%d %d %d",&n,&m,&k);
        for(int i=1; i<maxn; i++)f[i]=0;
        for(int i=2; i<=n; i++)
            add(i-1,i,1);
        for(int i=1; i<=m; i++)
        {
            int a,b,c,d;
            scanf("%d %d %d %d",&a,&b,&c,&d);
            if(a==b&&c==d)
            {
                add(b,c,k);
                add(c,b,-k);
            }
            else
            {
                add(c,b,1-k);
                add(a,d,k+1);
            }
        }
        if(spfa())
        {
            printf("Case #%d:",cn);
            for(int i=2;i<=n;i++)
                printf(" %d",dis[i]-dis[i-1]);
            cout<<endl;
        }
        else
            printf("Case #%d: IMPOSSIBLE
",cn);
    }
    return 0;
}

分析

ym：差分打表，会发现差分结果差21，推出一个多项式，但要用高精度，但Java不熟悉耽误了半天时间

Summary：

ym：没加Case 贡献一发罚时，x，y搞反了贡献一发罚时，震惊，ym贡献了全队2/3的罚时

czh:

hxx: