WNJXYK
Thanks to the cruel world.
WNJXYKのBlog
Codeforces #503
Codeforces #503

A. Elections

n个候选人和n个小团体,现在知道每个候选人的选择p_i。可以做一个操作就是花c_i的金钱收买第i个人,让他选择指定团体。
问如果让第1个团体以绝对优势获胜(获得投票大于其他所有团体),所需要的花费的最少金钱是多少。

我们枚举第1个团体最后获得的票数是多少,在知道最终票数的情况下,我们就能推测需要收买多少选择其他团体的人。执行这个过程,然后计算并比较出最小代价即可。

/**
* Author : WNJXYK
* Date : 20180814
* Problem : 1019A
**/

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long LL;
typedef pair<int,int> PII;

const LL MOD=998244353;
const int MAXN=1e5+50;

LL powmod(LL a, LL b) {LL res=1;a%=MOD; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%MOD;a=a*a%MOD;}return res;}
LL gcd(LL a, LL b) { return b?gcd(b,a%b):a;}

int n, m;
struct Voters{
    int party, money;
    bool enbled;
}vote[MAXN];
int party[MAXN], dead[MAXN];
LL ans=0;

inline bool cmp(const Voters &a, const Voters &b){
    if (a.money!=b.money) return a.money<b.money;
    return a.party<b.party;
}

inline void solve(int T){
    scanf("%d%d", &n, &m);
    ans=0;
    for (int i=1; i<=n; i++){
        scanf("%d%d", &vote[i].party, &vote[i].money);
        party[vote[i].party]++;
        ans+=vote[i].money;
    }

    sort(vote+1, vote+n+1, cmp);
    for (int i=party[1]; i<=n; i++){
        LL cost=0; int now=party[1];
        for (int j=1; j<=m; j++) dead[j]=0;
        for (int j=1; j<=n; j++) vote[j].enbled=true;
        for (int j=1; j<=n; j++){
            if (vote[j].party==1) continue;
            int p=vote[j].party, m=vote[j].money;
            if (i<=party[p]-dead[p]){
                ++dead[p]; ++now;
                vote[j].enbled=false;
                cost+=m;
            }
        }
        if (now>i) continue;
        for (int j=1; j<=n && now<i; j++){
            if (vote[j].party==1 || vote[j].enbled==false) continue;
            cost+=vote[j].money; ++now;
        }
        ans=min(ans, cost);
    }

    printf("%lld\n", ans);
}

int main(){
    //freopen("in.txt" ,"r", stdin);
    //freopen("out.txt", "w", stdout);
    solve(0);
    return 0;
}

B. The hat

n个人坐成一个圈,每个人的编号和其相邻的人的编号之差为\pm 1。现在想知道是否存在一对面对坐着的人(ii+\frac{n}{2}),他们的编号相同。(n\leq100,000)
交互题,使用不超过60次询问找出这对人(如果不存在,输出-1)

我们可以发现,如果这个圈的长度的一半是奇数,那么对着做的人编号肯定不相同,因为需要经过奇数次\pm 1,相对位置的数字数值的奇偶性一定不同,所以当n不是4的倍数的时候,一定找不到。

一段\pm 1的数列,要找到一段长度为\frac{n}{2}的区间,使得这段区间的求和为0。我们可以知道,这个区间的值是准连续变化的(0, \pm 2),所以我们只需要二分这个区间的左端点,看看不断缩小区间和左右端点和为异号的区间即可。

/**
* Author : WNJXYK
* Date : 20180816
* Problem : 1019B
**/

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long LL;
typedef pair<int,int> PII;

const LL MOD=998244353;
const int MAXN=1e5+50;

LL powmod(LL a, LL b) {LL res=1;a%=MOD; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%MOD;a=a*a%MOD;}return res;}
LL gcd(LL a, LL b) { return b?gcd(b,a%b):a;}

inline int Query(int x){
    printf("? %d\n", x);
    fflush(stdout);
    static int ret=0; scanf("%d", &ret);
    return ret;
}

inline void Print(int x){
    printf("! %d\n", x);
    fflush(stdout);
}

inline void solve(int T){
    int n; scanf("%d", &n);
    if (n%4!=0) { Print(-1); return; }
    int lv=Query(1), rv=Query(n/2+1);
    if (lv==rv){ Print(n/2+1); return; }
    int sgn=(lv>rv);
    int left=1, right=n/2+1;
    while(left+1<right){
        int mid=(left+right)/2, opMid=mid+n/2;
        int mv=Query(mid), ov=Query(opMid);
        if (mv==ov) { Print(mid); return; }
        if (sgn==(mv>ov)){
            left=mid;
        }else right=mid;
    }
    for (int i=left; i<=right; i++){
        int v1=Query(i), v2=Query(i+n/2);
        if (v1==v2){ Print(i); return; }
    }
    Print(-1);
}

int main(){
    //freopen("in.txt" ,"r", stdin);
    //freopen("out.txt", "w", stdout);
    solve(0);
    return 0;
}

赞赏
https://secure.gravatar.com/avatar/f83b57c055136369e9feba5d6671d6b5?s=256&r=g

WNJXYK

文章作者

一个蒟蒻

发表评论

textsms
account_circle
email

WNJXYKのBlog

Codeforces #503
A. Elections 有$$n$$个候选人和$$n$$个小团体,现在知道每个候选人的选择$$p_i$$。可以做一个操作就是花$$c_i$$的金钱收买第$$i$$个人,让他选择指定团体。 问如果让第1个团体以绝对优…
扫描二维码继续阅读
2018-08-14
<--! http2https -->