all_dream 笔试

NOIP

by 陈伟文

1.求排列逆序数

思路：树状数组求逆序对

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 7;
struct binaryIndexTree{
    int val[N], n;
    inline void init(int n){
        this->n = n;
        memset(val, 0, sizeof(val));
    }
    inline void add(int k, int num){
        for (;k <= n; k += k&-k) val[k] += num;
    }
    int sum(int k){
        int sum = 0;
        for (; k; k -= k&-k) sum += val[k];
        return sum;
    }
} T;
int main(){
    //freopen("in.txt", "r", stdin);
    // 思路：树状数组求逆序对裸题
    for (int n; ~scanf("%d", &n);){
        T.init(n);
        LL sum = 0; // ans may larger than INT_MAX
        for (int x, i = 0; i < n; i++){
            scanf("%d", &x); // input
            sum += T.sum(n) - T.sum(x - 1); // sum[x..n]
            T.add(x, 1);
        }
        printf("%lld\n", sum);
    }
}

2.装箱问题

思路：01背包

#include <bits/stdc++.h>
using namespace std;
const int N = 33;
const int V = 2e4 + 7;
int v[N]; // 每个箱子容量
int f[N][V]; //
int main(){
    //freopen("in.txt", "r", stdin);
    for (int cap, n; ~scanf("%d%d", &cap, &n);){
        for (int i = 1; i <= n; i++){
            scanf("%d", &v[i]);  // just input
        }
        memset(f, 0, sizeof f);
        f[0][0] = true;
        for (int i = 1; i <= n; i++){
            for (int j = 0; j <= cap; j++){
                f[i][j] = f[i-1][j]; // ignore v[i]
                if (v[i] <= j){ // v[i] not too large
                    f[i][j] |= f[i-1][j-v[i]]; // pack v[i]
                }
            }
        }
        int ans = 0;
        for (int i = 0; i <= cap; i++){
            if (f[n][i]) ans = i;
        }
        printf("%d\n", cap - ans);
    }
    return 0;
}

3.仙岛求药

思路：bfs

#include <bits/stdc++.h>
using namespace std;
const int N = 22;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
struct node{
    int x, y, step;
    node(){}
    node(int _x, int _y, int s):x(_x), y(_y),step(s){}
};
int m, n;
int g[N][N]; // grid
bool vis[N][N]; // visited
inline int bfs(int sx, int sy, int tx, int ty){
    queue <node> Q;
    Q.push(node(sx, sy, 0));
    memset(vis, 0, sizeof(vis));
    vis[sx][sy] = true;
    for (; !Q.empty();){
        node now = Q.front(); Q.pop();
        if (now.x == tx && now.y == ty) return now.step;
        for (int i = 0; i < 4; i++){
            int cx = now.x + dx[i];
            int cy = now.y + dy[i];  // new position
            if (cx<1 || cx>m || cy<1 || cy>n) continue;
            if (vis[cx][cy] || g[cx][cy]) continue;
            vis[cx][cy] = true;
            Q.push(node(cx, cy, now.step+1));
        }
    }
    return -1;
}
int main(){
    //freopen("in.txt", "r", stdin);
    char st[N];
    for (int sx, sy, tx, ty; ~scanf("%d%d\n", &m, &n);){
        if (m == 0 && n == 0) break;
        for (int i = 1; i <= m; i++){
            scanf("%s\n", st);
            for (int j = 0; j < n; j++){
                if (st[j] == '#') g[i][j+1] = 1; // monster
                else{
                    g[i][j+1] = 0; // can walk
                    if (st[j] == '@') sx = i, sy = j + 1; // start x, y
                    if (st[j] == '*') tx = i, ty = j + 1; // target x, y
                }
            }
        }
        int ans = bfs(sx, sy, tx, ty);
        printf("%d\n", ans);
    }
    return 0;
}

4.画家问题

思路：枚举

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
using namespace std;
const int N = 22;
const int INF = 0x3f3f3f3f;
int g[N][N], temp[N][N], row[N];
int n, cnt;
void meiju(int x){ // ugly name, sorry
    memset(row, 0, sizeof(row));
    for (int i = 0; x; x >>= 1) row[i++] = x&1;
}
void paint(int x,int y){
    temp[x][y] ^= 1;
    if (x-1 >= 0) temp[x-1][y] ^= 1;
    if (y-1 >= 0) temp[x][y-1] ^= 1;
    if (x+1 < n) temp[x+1][y] ^= 1;
    if (y+1 < n) temp[x][y+1] ^= 1;
    cnt++;
}
int check(){
    for(int i = 1; i < n; ++i){
        for(int j = 0; j < n; ++j){
            if(temp[i-1][j] != 1)paint(i,j);
        }
    }
    for(int i = 0; i < n; ++i){
        if(temp[n-1][i] != 1) return INF; //not all yello, failed
    }
    return cnt;
}
int main(){
    //freopen("in.txt", "r", stdin);
    int _;
    scanf("%d", &_);
    for (; _--;){
        scanf("%d", &n);
        int ans = INF;
        char s[16];
        for(int i = 0; i < n; ++i){  // just input
            scanf("%s", s);
            for(int j = 0; j < n; ++j){
                if (s[j] == 'w') g[i][j] = 0;
                else g[i][j] = 1;
            }
        }
        int k = pow(2.0, n);
        for(int i = 0; i < k; ++i){
            meiju(i);
            cnt = 0; // init
            memcpy(temp, g, sizeof g);
            for(int j = 0; j < n; ++j){
                if (row[j] == 1) paint(0, j);
            }
            ans = min(ans, check());
        }
        if (ans == INF) puts("inf");
        else printf("%d\n", ans);
    }
    return 0;
}

5.全排列

思路：STL小练习

#include <bits/stdc++.h>
typedef long long LL;
using namespace std;
int a[] = {0, 1, 2, 3, 4, 5};
int main(){
    string s;
    cin >> s;
    do{
        for (int i = 0; i < s.size(); i++){
            cout << s[a[i]];
        }
        puts("");
    }while(next_permutation(a, a+s.size()));
}