8月11日 Codeforces Round #503
题目链接:http://codeforces.com/contest/1020

A – New Building for SIS & B – Badge

过水,不说。。

C – Elections

思路:
算是一个比较简单的模拟(但是好像有大佬有$O(nlogn)$的做法)。。。枚举要得到多少选票,设为$x$,如果有其他党的选票大于x,就直接花钱买直到那个党选票小于x,如果这样最后选票不够x的话,就随便买选票直到有x张。这里买选票当然是尽可能买便宜的,然后总复杂度是$O(n^3)$的。

比赛时T了一发,然后大力卡了一下常数过了pretest。结果就很愉快地的因为TLE FST了….后面把最外层循环从1-n改为1-n/2+1就A了,想想自己真TM傻,卡常时这个都没有注意到。

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
#define LL long long
#define MAXN 3005
#define INF 1e18
using namespace std;

int n, m, p[MAXN], num[MAXN];
LL c[MAXN], ans=INF;

struct A {int p, tag; LL c;} a[MAXN];

void read1(LL &x)
{
    int f=1;x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    x*=f;
}

void read2(int &x)
{
    int f=1;x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    x*=f;
}

bool CMP1(A x, A y)
{
    if(x.p!=y.p) return x.p<y.p;
    else return x.c<y.c;
}

bool CMP2(A x, A y)
{
    return x.c<y.c;
}

int main()
{
    read2(n); read2(m);
    for(register int i=1; i<=n; ++i) read2(a[i].p), read1(a[i].c), num[a[i].p]++;
    for(register int i=1; i<=n/2+1; ++i)
    {
        sort(a+1, a+n+1, CMP1);
        for(register int j=1; j<=n; ++j) a[j].tag=0;
        LL cost=0; int res=0, pnt=1;
        for(register int j=1; j<=m; ++j)
        {
            if(j==1)
            {
                pnt+=num[j];
                res+=num[j];
                continue;
            }
            for(register int k=pnt; k<=pnt+num[j]-i; ++k)
            {
                cost+=a[k].c; a[k].tag=1;
                res++;
            }
            pnt+=num[j];
        }
        sort(a+1, a+n+1, CMP2);
        for(register int j=1; res<i; ++j)
        {
            if(a[j].tag || a[j].p==1) continue;
            res++;
            cost+=a[j].c;
        }
        ans=min(ans, cost);
    }
    printf("%lld\n", ans);
}

D – The hat

思路:
交互题,比赛时少看到一个条件连题目都没有弄懂。菜死了QWQ

相邻的同学手上数字不会相差超过1,这是一个很神奇的条件。我们设数组$b[i]=a[i]-a[i+n/2]$,根据上面的条件可以发现$b[i]-b[i+1]$只能为$\lbrace -2, 0, 2 \rbrace$,在某种意义下我们可以把数组$b$的取值视为是连续的,这个性质也很有意思。

显然有$b[i]=-b[i+n/2]$,答案也就是求一点$i$使得$b[i]=0$。因为上面的性质,我们就可以使用二分求解。有一点要注意的是如果$b$中有一个元素为奇数时,那么$b$中的所有元素都是奇数,这样就直接输出-1。

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define MAXN 100005
using namespace std;

int n, ans, a[MAXN], b[MAXN];

int main()
{
    scanf("%d", &n);
    printf("? %d\n", 1); fflush(stdout);
    scanf("%d", &a[0]);
    printf("? %d\n", n/2+1); fflush(stdout);
    scanf("%d", &a[n/2]);
    b[0]=a[0]-a[n/2]; b[n/2]=a[n/2]-a[0];
    if(b[0]%2) {printf("! -1\n"); fflush(stdout); return 0;};
    int l=0, r=n/2;
    while(1)
    {
        int mid=(l+r)/2;
        printf("? %d\n", mid+1); fflush(stdout);
        scanf("%d", &a[mid]);
        printf("? %d\n", n/2+mid+1); fflush(stdout);
        scanf("%d", &a[n/2+mid]);
        b[mid]=a[mid]-a[n/2+mid];
        if(b[mid]==0) {ans=mid; break;}
        if(b[mid]*b[l]<0) r=mid;
        else l=mid;
    }
    printf("! %d", ans+1);
}

E – Sergey’s problem

思路:
神题啊。。。首先有一个很简单的思路,假设一个确定了$1~i-1$号节点的集合,那么对于$i$号节点,如果集合中的点不与节点$i$相邻,那么就把$i$号节点加入集合中。

那么这样就会有一个问题,就是可能会有节点无法加入集合,并且集合中的点无法到达它(CF上第三个点就能够HACK掉)。于是我们先从小到大扫一遍确定出一个集合,集合内编号小的点不会向编号大的点连边。然后从大到小扫一遍这个集合,如果编号大的点有一条边连向了集合内编号小的点,那就把编号小的点移除集合。这样就可以保证满足题目的条件,因为第二遍移出集合的点一定能一步内到达,第一遍移出集合的点一定能两步内到达。

代码:

#include <iostream>
#include <cstring>
#include <cstdio>
#define MAXN 1000005
using namespace std;

int n, m, cnt, top, head[MAXN], ans[MAXN];
bool vis[MAXN];

struct Edge {int next, to;} edge[MAXN];

void addedge(int from, int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        addedge(x, y);
    }
    for(int i=1; i<=n; i++)
        if(!vis[i]) for(int j=head[i]; j; j=edge[j].next)
                if(edge[j].to>i) vis[edge[j].to]=1;
    for(int i=n; i>=1; i--)
        if(!vis[i])
        {
            ans[++top]=i;
            for(int j=head[i]; j; j=edge[j].next) vis[edge[j].to]=1;
        }
    printf("%d\n", top);
    for(int i=1; i<=top; i++) printf("%d ", ans[i]);
}

发表评论

邮箱地址不会被公开。 必填项已用*标注