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;
}

题意：给定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;
}

题意：给定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;
}

题意：搜索

#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;
}