2018-12-5 及 codeforces round 525v2

突然发现五天没记录了，这五天学习完全没有按着正常规划进行，先罗列一下吧。

机器学习视频第一周的全部看完了。
算法导论看了几页。
参加了一次CF。rating只加了20，看来提高实力才是最关键的。
C++找到了侯捷老师的视频。
貌似记不得什么了。

记录一下昨天的CF题解吧。

题目链接：http://codeforces.com/contest/1088

A题：理论上可以用暴力搜，但是除一之外所有的答案都可以写成"x x",不再写代码解释。

B题：题意为数组中的每一个数每次都减去一个最小的数，并输出这个数。可以先排序，然后下面展示的是O(n)复杂度的算法。

#include<iostream>

#include<vector>

#include<cstdio>

#include<algorithm>

using namespace std;

int a[100005];

int main(){

    int n,k;

    scanf("%d%d",&n,&k);

    for(int i = 0; i < n; i++){

        scanf("%d",&a[i]);

    }

    sort(a,a+n);

    int sumsub = 0;

    int j = 0;

    while(k--){

        while(j <n && a[j] <= sumsub) j++;

        if(j == n) printf("0\n");

        else {

            printf("%d\n",a[j]-sumsub);

            sumsub = a[j];

        }

    }

    return 0;

}

C题：题目提到了两个操作，要求在n+1个操作之内讲数组变为升序。可以转化为前n个操作讲n个数对n+1的余数变为递增，然后最后一步对n+1取模。

#include<iostream>

#include<cstdio>

#include<vector>

using namespace std;

int a[10000];

vector<pair<int,int>> ans;

int main(){

    int n ;

    scanf("%d",&n);

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

        scanf("%d",&a[i]);

    }

    int cnt = 0;

    int sum = 0;

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

        if((sum+a[i])%(n+1) == i) continue;

        else {

            cnt++;

            int d = (sum+a[i])%(n+1);

            if(i > d) {ans.push_back(make_pair(i,i-d));sum+=i-d;}

            else {ans.push_back(make_pair(i,n+1+i-d));sum+=n+1+i-d;}

        }

    }

    cnt++;

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

    for(int i = 0; i < cnt-1;i++){

        printf("1 %d %d\n",ans[i].first,ans[i].second);

    }

    printf("2 %d %d",n,n+1);

    return 0;

}

D题思路是对的，但是因为一些原因没有去做，不然可能这次就上蓝了。

#include<iostream>

using namespace std;

int query(int a,int b){

    cout << "? "<<a<<" "<<b<<endl;

    int res;

    cin >> res;

    return res;

}

int a = 0,b = 0;

int main(){

    bool comp = (query(0,0) == 1);

    for(int i = 29; i >= 0; i--){

        int p = query(a,b|1<<i);

        int q = query(a|1<<i,b);

        if(p == 1 && q == -1){

            a = a|1<<i;

            b = b|1<<i;

        }else if( p == -1 && q == 1){

            continue;

        }else{

            if(comp) a = a|1<<i;

            else b = b|1<<i;

            comp = (p==1);

        }

    }

    cout << "! "<<a<<" "<<b<<endl;

    return 0;

}

巴特西

2018-12-5 及 codeforces round 525v2

以后每天都记录一下吧

最新文章

热门文章