首页 > 代码库 > NWERC 2011 ABCDEH 题解

NWERC 2011 ABCDEH 题解

2024-07-12 02:04:14   221人阅读

A：SPOJ NWERC11A A - Binomial coefficients

题解：点击打开链接

B: 点击打开链接  

Bird tree

从下到上发现是个gcd的过程（辗转相除

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int a, b;
        scanf("%d/%d", &a, &b);
        while (a - b) {
            if (a > b) {
                putchar('R');
                a -= b;
            } else {
                putchar('L');
                b -= a;
            }
            swap(a, b);
        }
        puts("");
    }
    return 0;
}

C:点击打开链接

Movie collection

#include <cstdio>
#include <algorithm>
typedef long long ll;
const int N = 100005 * 3;
int pos[N], a[N], nn;
void clear() {
	for(int i = 0; i <= nn; i ++) {
		a[i] = 0;
	}
}
void update(int idx, int val) {
    while( idx <= nn ) {
    	a[idx] += val;
		idx += idx & (-idx);
    }
}
int sum(int idx) {
	int s = 0;
	while(idx > 0) {
		s += a[idx];
		idx -= idx & (-idx);
	}
	return s;
}

int main() {
	int T;scanf("%d", &T);
	int n, m, x;
	while(T-- > 0) {
		scanf("%d%d", &n, &m);
		nn = n + m;
		clear();
		for(int i = 1; i <= n; i ++) {
			pos[i] = i+m;
			update(i+m, 1);
		}
		for(int i = m; i > 0; i --) {
			scanf("%d", &x);
			printf("%d", sum(pos[x]) - 1);
			if(i > 1) printf(" ");
			update(pos[x], -1);
			update(i, 1);
			pos[x] = i;
		}
		puts("");
	}
	return 0;
}

D:题目链接： http://www.spoj.com/problems/NWERC11D/ 

Piece it together

题解：点击打开链接

E: 点击打开链接

Please, go first

#include <cstdio>
#include <algorithm>
#include<iostream>
#include<string.h>
#include<vector>
using namespace std;
const int N = 300;

vector<int>G[N];
char s[30000];

int main() {
    int cas, idx, u, Q, n;
    scanf("%d", &cas);
    while (cas -- >0) {
        scanf("%d",&n);
        scanf("%s",s);
        for(int i = 0; i < N; i++)G[i].clear();
        for(int i = 0; i < n; i++) {
            G[s[i]].push_back(i);
        }
        int ans = 0;
        for(int i = 0; i < N; i++)if(G[i].size()){
            for(int j = 0; j < G[i].size()-1; j++) {
                ans += G[i][G[i].size()-1] - G[i][j];
            }
        }
        for(int i = 0; i < N; i++)
            if(G[i].size())
        {

            int len = G[i].size();
            len--;
            ans -= (1+len)*len/2;
        }
        cout<<ans*5<<endl;

    }
    return 0;
}
/*
99
2
AB
2
AA
6
ABABAB
10
AAAAAAAAAA
1
A
5
ABCDD
5
ABCDA

*/

H:点击打开链接

Tichu


题解：http://blog.csdn.net/qq574857122/article/details/37778285


联系
我们