Codeforces Round #209 (Div. 2)

点击打开链接

A. Table

题意：水题

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

int main(){
    int n , m , x;
    int ans = 4;
    scanf("%d%d" , &n , &m);
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < m ; j++){
            scanf("%d" , &x);
            if(x && (i == 0 || i == n-1 || j == 0 || j == m-1))
              ans = 2;
        }
    }
    printf("%d\n" , ans);
    return 0;

B. Permutation

题意：给定n个k，要求找到一个序列长度为2*n并且序列每个数1~2n区间的某个值。这个序列要满足. 

思路：对上面的等式进行化简可以得到|a1-a2| + |a3-a4| + ... + |a2i-1-a2i|  - | (a1-a2) + (a3-a4) + ... + (a2i-1-a2i)| = 2K , 并且题目规定2k <=
n 。

           由于这个序列的每个数是1~2n的某个值，那么如果让这个序列为1,2,3,4....2n-1,2n，那么等式的值为n-n = 0。通过观察等式我们可以知道|a1-a2| + |a3-a4| + ... + |a2i-1-a2i|这个式子的值和a1,a2，a3,a4的顺序无关，那么我们只要让| (a1-a2)
+ (a3-a4) + ... + (a2i-1-a2i)|这个式子的值为2k-n即可，其实就是变换k对的a的顺序。

代码：

// this is Problem B
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 50010;

int main(){
    int n , k;
    scanf("%d%d" , &n , &k);
    int ans[2*MAXN];
    for(int i = 1 ; i <= n*2 ; i += 2){
        ans[i] = i;
        ans[i+1] = i+1;
    }
    int j = 1;
    for(int i = 1 ; i <= k ; i++ , j+=2)
        swap(ans[j] , ans[j+1]);
    for(int i = 1 ; i < 2*n ; i++)
        printf("%d " , ans[i]);
    printf("%d\n" , ans[2*n]);
    return 0;
}

C Prime Number

题意：给定n个数和x，令 = t/s，求t和s的最大公约数

思路：我们可以把左边的式子进行化简，得到x^(sum-a1)+x^(sum-a2)+...+x^(sum-an) / x^sum

           由于分子和分母都是和x有关的等式，我们假设分子中的最小项为min，那么可以化简为

           x^(sum-a1)+x^(sum-a2)+...+x^(sum-an) / x^sum = min*a / b

           因为min是最小的，因此a和b的最小公约数为1，因此答案就是min，所以我们要求的就是min

           但是要注意的是假设分子中有多项的min，比如min = 2^2，但是现在有5项，即5*2^2，我们应该要进行升幂运算

代码：

#include<map>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long int64;
const int MOD = 1e9+7;
const int MAXN = 100010;

int n , x;
int num[MAXN];
int64 sum;
map<int64,int64>mp;

int64 quickPow(int64 m , int64 t){
    int64 sum = 1;
    while(t){
        if(t%2 == 1)
            sum = sum*m%MOD;
        m = m*m%MOD;
        t = t/2;
    }
    return sum%MOD;
}

void solve(){
    int64 ans = sum;
    map<int64 , int64>::iterator it;
    for(it = mp.begin() ; it != mp.end() ; it++){
        if(it->second >= x){
            mp[(it->first)+1] += (it->second)/x;
            (it->second) %= x;
        }
        if(it->second){
            ans = min(ans , it->first);
            break;
        }
    }
    ans = quickPow(x , ans);
    cout<<ans<<endl;
}

int main(){
    while(scanf("%d%d" , &n , &x) != EOF){
        sum = 0;
        for(int i = 0 ; i < n ; i++){
            scanf("%d" , &num[i]);
            sum += num[i];
        }
        mp.clear();
        for(int i = 0 ; i < n ; i++)
            mp[sum-num[i]]++;
        solve();
    }
    return 0;
}

D Pair of Numbers

题意：给定n个数，要求找到所有区间[l,r]，要求这个区间满足两个条件：区间内有一个数a[j]能够整除区间的任何数，并且r-l最大。输出有几个这样的区间和最大的r-l以及所有满足的区间的左端点

思路：暴力枚举每个数。假设当前数为a[i]，那么我们就以a[i]为除数，分别向左边和右边去扩展找到以它为除数的最大的满足区间，这样即可 

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 3*100010;

int n , num[MAXN];
int ans , out[MAXN];
int l[MAXN] , r[MAXN];

void solve(){
    // make left
    l[1] = 1;
    for(int i = 2 ; i <= n ; i++){
       if(num[i-1]%num[i] == 0){
           l[i] = l[i-1];
           int tmp = l[i];
           while(tmp > 1 && num[tmp-1]%num[i] == 0)
               tmp--;
           l[i] = tmp;
       }
       else
           l[i] = i;
    }
    // make right
    r[n] = n;
    for(int i = n-1 ; i >= 1 ; i--){
        if(num[i+1]%num[i] == 0){
           r[i] = r[i+1];
           int tmp = r[i];
           while(tmp < n && num[tmp+1]%num[i] == 0)
                tmp++;
           r[i] = tmp;
        }
        else
            r[i] = i;
    }
    ans = 0;
    for(int i = 1 ; i <= n ; i++)
        ans = max(ans , r[i]-l[i]);
    // make out
    int pos = 0;
    for(int i = 1 ; i <= n ; i++)
        if(ans == r[i]-l[i])
           out[pos++] = l[i];
    pos = unique(out , out+pos)-out;
    printf("%d %d\n%d" , pos , ans , out[0]);
    for(int i = 1 ; i < pos ; i++)
        printf(" %d" , out[i]);
    printf("\n");
}

int main(){
    while(scanf("%d", &n) != EOF){
        for(int i = 1 ; i <= n ; i++)
            scanf("%d" , &num[i]);
        solve();
    }
    return 0;
}

E Neatness

题意：搜索

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;

const int MAXN = 510;

int mat[MAXN][MAXN];
int n , sum , pos;
bool vis[MAXN][MAXN];
int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
char forwad[4] = {'U','R','D','L'};
char backwad[4] = {'D','L','U','R'};
char ans[MAXN*10000];

bool isOut(int x , int y){
    return (x < 1 || x > n || y < 1 || y > n);
}

bool check(int x , int y , int d){
    while(1){
        if(isOut(x , y) || vis[x][y])
            return false;
        if(mat[x][y])
            return true;
        x = x+dir[d][0];
        y = y+dir[d][1];
    }
}

void dfs(int x , int y){
    if(!mat[x][y]){
        mat[x][y] = 1;
        ans[pos++] = '1';
        sum++;
    }
    vis[x][y] = true;
    for(int i = 0 ; i < 4 ; i++){
        int tx = x+dir[i][0];
        int ty = y+dir[i][1];
        if(isOut(tx , ty) || vis[tx][ty] || !check(tx , ty , i))
            continue;
        ans[pos++] = forwad[i];
        dfs(tx , ty);
        ans[pos++] = backwad[i];
    }
    sum--;
    ans[pos++] = '2';
}

int main(){
    int x , y;
    while(scanf("%d%d%d" , &n , &x , &y) != EOF){
         sum = 0;
         for(int i = 1 ; i <= n ; i++){
             for(int j = 1 ; j <= n ; j++){
                 scanf("%d" , &mat[i][j]);
                 sum += mat[i][j];
             }
         }
         pos = 0;
         memset(vis , false , sizeof(vis));
         dfs(x , y);
         if(sum){
             puts("NO");
         }
         else{
             puts("YES");
             ans[pos] = '\0';
             puts(ans);
         }
    }
    return 0;
}
时间： 2024-08-20 16:15:30

Codeforces Round #209 (Div. 2)的相关文章

Codeforces Round #157 (Div. 1) C. Little Elephant and LCM （数学、dp）

C. Little Elephant and LCM time limit per test 4 seconds memory limit per test 256 megabytes input standard input output standard output The Little Elephant loves the LCM (least common multiple) operation of a non-empty set of positive integers. The

Codeforces Round #205 (Div. 2) / 353C Find Maximum (贪心)

Valera has array a, consisting of n integers a0,a1,...,an-1, and function f(x), taking an integer from 0 to 2n-1 as its single argument. Value f(x) is calculated by formula , where value bit(i) equals one if the binary representation of number xconta

Codeforces Round #201 (Div. 1) / 346A Alice and Bob:数论&amp;amp;想法题

A. Alice and Bob http://codeforces.com/problemset/problem/346/A time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output It is so boring in the summer holiday, isn't it? So Alice and Bob have inven

Codeforces Round #311 (Div. 2) B. Pasha and Tea

题目链接:http://codeforces.com/contest/557/problem/B 题意:给你n个boy,n个girl ,然后w表示茶壶的最大容量,然后n个茶杯,每个都有不同的容量,要求boy的茶杯里的茶水是girl的两倍,且boy和boy的容量一样,girl和girl的容量一样,问如何倒茶,求最大的倒茶量 #include <iostream> #include <cstdio> #include <algorithm> using namespace

Codeforces Round #299 (Div. 2) A. Tavas and Nafas

题目链接:http://codeforces.com/problemset/problem/535/A #include <iostream> #include <string> using namespace std; int main() { string s1[10]={"zero","one","two","three","four","five",&qu

Codeforces Round #308 (Div. 2) A. Vanya and Table

题目链接:http://codeforces.com/contest/552/problem/A hint: 就是求几个矩形的面积 #include <iostream> #include <cmath> using namespace std; struct point { int x; int y; }a[2]; int main() { int m; while(cin>>m) { int sum=0; while(m--) { //注释的是方法一 cin>

Codeforces Round #311 (Div. 2) A. Ilya and Diplomas

题目链接:http://codeforces.com/contest/557/problem/A #include <iostream> using namespace std; int minn[3]; int maxx[3]; int main() { int m; while(cin>>m) { int ans[3]={0}; for(int i=0; i<3; i++) cin>>minn[i]>>maxx[i]; for(int i=0; i

Codeforces Round #308 (Div. 2) Vanya and Books

题目链接:http://codeforces.com/contest/552/problem/B 题意:就是求有几个数字: eg:13:1 2 3 4 5 6 4 7 8 9 1 0 1 1 1 2 1 3 一共17个数字 #include <iostream> using namespace std; long long a[12]={0,9,99,999,9999,99999,999999,9999999,99999999,999999999,9999999999}; int main()

Codeforces Round #307 (Div. 2) A

http://codeforces.com/contest/551/problem/A #include <iostream> using namespace std; int data[2005]; int main() { int m; while(cin>>m) { for(int i=0; i<m; i++) cin>>data[i]; for(int i=0; i<m; i++) { int ans=1; for(int j=0; j<m;