题目链接:点击打开链接
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) 题解