活动安排 #include <bits/stdc++.h> #define x first #define y second using namespace std; typedef pair<int, int> PII; const int N = 1010; int n; PII q[N]; int main() { cin >> n; for(int i = 0; i < n; i ++) cin >> q[i].y >> q[i].x; sort(q, q + n); int cnt = 0, end = -1; for...

[NOIP2010]数字统计 杀鸡用牛刀了属于是 # include <iostream> # include <cmath> using namespace std; int dgt(int n) // 计算整数n有多少位 { int res = 0; while (n) res ++, n /= 10; return res; } int cnt(int n, int i) // 计算从1到n的整数中数字i出现多少次 { int res = 0, d = dgt(n); for (int j = 1; j <= d; j ++) // 从右到左第j位上数字i出...

[NOIP2011]数字反转 #include <bits/stdc++.h> using namespace std; int n; int main() { cin >> n; if(n < 0) { n = -n; cout << '-'; } int res; while(n) { res = res * 10 + n % 10; n /= 10; } cout << res; return 0; }

[NOIP2013]表达式求值 #include <iostream> using namespace std; int n,m,ans; char c; int main() { cin >> n; while(~scanf("%c%d",&c,&m)) { if(c == '+') ans += n,n = m; else if(c == '*') n *= m; ans %= 10000; n %= 10000; } cout << (ans + n) % 10000; }

好吧，说实话我还以为是计数类DP,没想到完全想复杂了,不过我这是万能的，可以求任意x~y直接任意z的出现次数，用前缀和就行cnt(y,z) - cnt(x-1,z) # include <iostream> # include <cmath> using namespace std; int dgt(int n) // 计算整数n有多少位 { int res = 0; while (n) ++ res, n /= 10; return res; } int cnt(int n, int i) // 计算从1到n的整数中数字i出现多少次 { int res = 0, d ...

#include<iostream> using namespace std; const int N = 1010; int a[N],res[N]; int n,s; int main() { cin >> n; res[0] = a[0] = 1; for(int i = 2;i <= n;i++) { for(int j = 0;j < N;j++) { a[j] = s + a[j] * i; s = a[j] / 10; a[j] %= 10; } for(int j = 0;j < N-1;j++) { res[j] += a[j]; r...

完全背包 #include<iostream> #include<algorithm> #include<cstring> using namespace std; int t; int n,m; int a[410]; int dp[80010]; int main() { cin >> t; while(t--) { cin >> n >> m; for(int i = 1;i <= n;i ++) cin >> a[i]; sort(a+1,a+n+1); memset(dp,0,sizeof(dp...

O(n)做法 数论 #include<iostream> using namespace std; int cnt[100010]; int n,k,sum,t; long long ans; int main() { cin >> n >> k; cnt[0] = 1; for(int i = 1;i <= n;i ++) { cin >> t; (sum += t) %= k; ans += cnt[sum]++; } cout << ans; return 0; }

终于开始dp了

完全背包 #include<iostream> using namespace std; const int N = 1e4 + 10; int n,m; int v[N],w[N],f[N]; int main() { cin >> m >> n; for(int i = 1;i <= n;i ++) { cin >> w[i] >> v[i]; for(int j = v[i];j <= m;j ++) f[j] = max(f[j],f[j-v[i]]+w[i]); } cout << f[m]; ret...