Tutorial CodeForces Round 289 (Div.2) (Second Winter Computer Camp Selection 2015) 题解

题目链接:点击打开链接

A:

#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <cstring>
#include <cmath>
#include <string>
using namespace std;

int a[12][11];

int main() {
    for (int i = 0; i <= 10; ++i) a[i][0] = a[0][i] = 1;
    for (int i = 1; i <= 10; ++i) {
        for (int j = 1; j <= 10; ++j) {
            a[i][j] = a[i - 1][j] + a[i][j - 1];
        }
    }
    int n;
    scanf("%d", &n);
    printf("%d\n", a[n - 1][n - 1]);
    return 0;
}
B:构造

#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <cstring>
#include <cmath>
#include <string>
using namespace std;
typedef long long ll;
const int N = 105;
int n, m;
int a[N];
int main() {
    while (~scanf("%d %d", &n, &m)){
        int mi = 1000, mx = 0;
        for (int i = 1; i <= n; i++){
            scanf("%d", &a[i]);
            mi = min(mi, a[i]);
            mx = max(mx, a[i]);
        }
        if (mx - mi > m)puts("NO");
        else {
            puts("YES");
            for (int i = 1; i <= n; i++){
                for (int j = 1; j <= mi; j++)printf("%d ", 1);
                a[i] -= mi;
                for (int j = 1; j <= a[i]; j++)printf("%d ", j); puts("");
            }
        }
    }
    return 0;
}
C:模拟

题意:有一个n长的严格单调递增序列,对于序列上某个点的权值就是数位和(即 123的数位和为6)

现在给出这个序列的数位和,构造一个序列使得最后一个数最小。

略麻烦,首先我们得到一个结论:对于给定的sum[i],我们目标是构造最小的且比前面的数大的数。

一定是构造最小的数,因为大的数我们也能用sum[i]构造,倒不如构造最小的。

构造时先判断是否需要进位(即位数能不能和上一个数字一样)

然后暴力递增即可。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <cstring>
#include <cmath>
#include <string>
using namespace std;
typedef long long ll;
const int N = 305;
int n;
int Ni(vector<int>&x){//返回最低位且不为9的位置,若全为9返回-1
    for (int i = 0; i < x.size(); i++)if (x[i] != 9)return i;
    return -1;
}
void add(vector<int>&x){//让x的数位和增加1
    int ni = Ni(x); 
    if (ni == -1){//全为9时想要让数位和增加1只能在最高位添一个1
        x.push_back(1);
    }
    else {
        x[ni]++;
    }
}
void hehe(vector<int>&now, vector<int>&old, int sum, int l){//当位数比上一个数字要大时,我们先构造一个100···这样的序列,且使得这个序列位数最少且全为9时的数位和>=sum,然后暴力增加数位和即可
    int dig = old.size() + 1;
    while (dig * 9 < sum){
        dig++;
    }
    dig--;
    now.clear();
    while (dig--)now.push_back(0); now.push_back(1);
    sum--;
    while (sum--)add(now);
}
void work(vector<int>&now, vector<int>&old, int sum,int l){
    if (l < sum){//如果数位和已经比上一个数大就直接从上一个数开始增加数位和
        now = old;
        sum -= l;
        while (sum--)add(now);
        return;
    }
    else {
        if (Ni(old) == -1 || old.size() * 9 < sum){
            hehe(now, old, sum, l);
            return;
        }
        now = old;
        int s = 0;
        int find = -1;
        for (int i = now.size()-1; i >= 0; i--){//如果我们把上一个数的某一位 find 增加1,然后把个位到find位全变0,能使得数位和<=sum 那么我们就不必增加位数,否则还是要增加位数
            s += now[i];
            if (now[i] < 9 && s + 1 <= sum){
                find = i;
            }
        }
        if (find!=-1){
            now[find]++;
            for (int i = 0; i < find; i++)now[i] = 0;
            int ssum = sum;
            for (int i = 0; i < now.size(); i++)ssum -= now[i];
            if (ssum >= 0){
                while (ssum--){ add(now); }
                for (int i = now.size() - 1; i >= 0; i--)if (now[i]>old[i])
                return;
                else if (now[i] < old[i])break;
            }
        }
        hehe(now, old, sum, l);     
    }
}
vector<int>u[2];

int main() {
    while (~scanf("%d", &n)){
        u[0].clear(); u[1].clear();
        u[1].push_back(0);
        int cur = 0, last = 1;
        int sum, l = 0;
        while (n--){
            scanf("%d", &sum);
            work(u[cur], u[last], sum, l);
            for (int i = u[cur].size() - 1; i >= 0; i--)putchar('0' + u[cur][i]);
            puts("");
            l = sum;
            cur ^= 1; last ^= 1;
        }
    }
    return 0;
}
/*
5
1
1
1
11
6
*/
D:

还不会,



E:

#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <cstring>
#include <cmath>
#include <string>
using namespace std;

const int MAX_N = 500007;

int bit[MAX_N << 1], len;

int sum(int i) {
    int s = 0;
    while (i > 0) {
        s += bit[i];
        i -= i & -i;
    }
    return s;
}

void add(int i, int x) {
    while (i <= len) {
        bit[i] += x;
        i += i & -i;
    }
}

char str[MAX_N];

bool is(char ch) {
    return ch == 'A' || ch == 'E' || ch == 'I' || ch == 'O' ||
    ch == 'U' || ch == 'Y';
}

long long z[MAX_N];
long long zz[MAX_N];

int main() {
    scanf("%s", str + 1);
    len = strlen(str + 1);
    for (int i = 1; str[i]; ++i) {
        if (is(str[i])) z[i] = z[i - 1] + 1;
        else z[i] = z[i - 1];
    }
    for (int i = 1; i <= len; ++i) {
        zz[i] = zz[i - 1] + z[i];
    }
    

    double ans = 0;
    for (int i = 0; i <= len; ++i) {
        if (len - (i + 1) >= 0) 
            ans += (zz[len] - zz[len - (i + 1)] - (zz[i])) * 1. / (i + 1);
    
    }
    printf("%f\n", ans);
    return 0;
}


F:dp[l][r]表示 区间[l,r] 构成一棵树的方法数。

对于一个区间[l, r] 构成一棵树,则点l一定是根,然后枚举2个区间相乘即可

dp[l][r] = dp[l+1][i] * dp[i+1][r] ( i = [l+1, r] )

当然 a[i+1] > a[l+1] ,这样才会满足题目中的暴力代码。。==

import java.io.PrintWriter;
import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Stack;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.Queue;

public class Main {
	int n;
	int[] a = new int[N];
	long[][] dp = new long[N][N];
	long dfs(int l, int r){
		if(dp[l][r] != -1)return dp[l][r];
		if(l >= r)return dp[l][r] = 1;
		long ans = 0;
		for(int i = l+1; i <= r; i++)
			if(i == r || a[i + 1] > a[l + 1])
				ans = (dfs(l+1, i) * dfs(i, r)+ans)%mod;	
		return dp[l][r] = ans;
	}
	void work() {
		while(cin.hasNext()){
			n = cin.nextInt(); for(int i = 1; i <= n; i++)a[i] = cin.nextInt();
			for(int i = 1; i <= n; i++){
				for(int j = i; j <= n; j++)dp[i][j] = -1;
			}
			System.out.println(dfs(1, n));
		}
	}

	Main() {
		cin = new Scanner(System.in);
		out = new PrintWriter(System.out);
	}

	public static void main(String[] args) {
		Main e = new Main();
		e.work();
		out.close(); 
	}

	public Scanner cin;
	public static PrintWriter out;
	static int N = 505;
	DecimalFormat df=new DecimalFormat("0.0000");
	static int mod = 1000000007 ;
}







Tutorial CodeForces Round 289 (Div.2) (Second Winter Computer Camp Selection 2015) 题解

上一篇:由window.history.back()引发的问题


下一篇:C#-numericUpDown-数字选择---ShinePans