Qualification Round Problem A. Speaking in Tongues 简单的按规律替换字符串 Problem B. Dancing With the Googlers 忘记了具体内容了，反正要注意边界特殊情况。 Problem C. Recycled Numbers 比赛时想不明白 Case #4，于是没交大数据，后来看了 Contest Analysis 才知道有1212这种情况，会重复。比赛的时候移位是用字符串实现的。。后来才改过来。看了代码 Contest Analysis 的才知道不用数组记录数字是否出现的，只要移回原数就退出，即可避免循环节的问题。 #include <iostream> #include <cstdio> using namespace std; int a, b; long long ans; void work(int num) { int temp = num; int base = 1; [...]
USTC1305 Maximum income
来自 xw 和 wh： 维护一个递减的单调队列，因为后入队的数只有比前面所有的数小才有可能成为符合条件区间的起点，若不满足这个条件，就二分找当前最大区间。复杂度 nlogn。 === 最近好忙= = #include <iostream> #include <cstdio> #include <cstring> using namespace std; const int MAXN = 100010; int a[MAXN]; int queue[MAXN]; int day[MAXN]; int main() { int t; int n, c; int p, ans; cin >> t; while (t–) { scanf("%d%d", &n, &c); for (int i = 0; i [...]
USTC1300 Big grid
USTC1300 DP，dp[i][SAME 或 DIFF] 表示格子[0][i]和[1][i-1]相同颜色或不同颜色有多少种情况。然后就很好写了。 数学解法不会= = #include <iostream> #include <cstdio> #include <cstring> using namespace std; const int SAME = 1; const int DIFF = 0; long long dp[10010][2]; int main() { int t,n,m,k; long long ans; cin >> t; while (t–) { memset(dp, 0, sizeof(dp)); scanf("%d%d%d", &n, &m, &k); if (n == 1) { [...]
HDU4193 Non-negative Partial Sums
HDU4193 终于知道单调队列了！其实挺简单的。搜到了这个：补缺补漏：单调队列- Blog of Felix021 – TechOnly 因为每个元素最多入队出队一次，所以复杂度是O(n)的。 这道题怎么做呢？开一个 2n 的数组，sum[i] 记录 a[1] 到 a[i] 的和。若在某个长度为 n 的区间里的最小 sum 大于等于区间左侧的 sum，也就是说区间里没有负数，答案计数加一。 // cin 会超时，不用 deque 会快一点 #include <iostream> #include <cstdio> #include <queue> using namespace std; const int MAXN = 2000010; int a[MAXN]; int main() { int n; while (scanf("%d", &n)) { if (n == 0) [...]
Codeforces Round #104 (Div. 2)
Codeforces Round #104 (Div. 2) Editorial 比赛时做出三题 A略 B忘了题意，也略吧… C Lucky Conversion 只需记录两字符串相应位置分别出现47和74的次数，输出这两个数的最大值 D Lucky Number 2 这个看了题解 想象删除所有相邻重复数字，可以得到形如47474747474747的串，所以 a3 与 a4 的差的绝对值一定小于等于1。然后分三种情况讨论： a3 = a4，若 a1 = a3，则说明4不够多，生成的串以7开头，如74747，多余的7插入到最右面，多余的4放在最左边的4。。否则形如47474，多余的7插入到最右面的7，多余的4放在最左边。 a3 > a4，形如47474747，多余的4放在最前面，7放在最后面 a3 < a4，形如74747474，多余的4插入到1位置，7插入到最后面的7 #include <iostream> #include <cstdlib> #include <cstdio> #include <string> using namespace std; int main() { int a1, a2, a3, a4; cin [...]
HDU4096 Universal Question Answering System
其实是2010年上海赛区F题，现场读入数据就写了很久…交上去之后是个诡异的错误，现在忘了是啥错误了… 连边判断连通性即可。这个题比较坑人…输入数据就比较恶心，当时还不会sscanf。名词和动词可能一样，所以需要两个map来存，还可能直接问are cat cat?要输出Y… BFS和DFS时间差不多… http://acm.fudan.edu.cn 还有数据呢。 #include <algorithm> #include <cstdio> #include <cstring> #include <iostream> #include <map> //#include <assert.h> using namespace std; const int N = 205; map<string, int> nmap, vmap; int mapcount; int getn(char* ch) { if (!nmap.count(ch)) nmap[ch] = mapcount++; return nmap[ch]; } int getv(char* ch) { if (!vmap.count(ch)) [...]
