CF328B Sheldon and Ice Pieces
题意：给定一个数字序列，问后面的数字元素能够组成最多的组数。
分析：把2和5,6和9看作是一个元素，然后求出一个最小的组数就可以了。
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cctype>
#include <algorithm>
using namespace std; char obj[];
char str[]; int digit[], rec[]; inline int get(char ch) {
if (ch == '') return ;
else if (ch == '') return ;
else return ch - '';
} int main() {
while (scanf("%s %s", obj, str) != EOF) {
memset(digit, , sizeof (digit));
memset(rec, , sizeof (rec));
int len1 = strlen(obj), len2 = strlen(str);
for (int i = ; i < len1; ++i) {
digit[get(obj[i])]++;
}
for (int i = ; i < len2; ++i) {
rec[get(str[i])]++;
}
int Min = ;
for (int i = ; i < ; ++i) {
if (digit[i] > ) {
Min = min(Min, rec[i] / digit[i]);
}
}
printf("%d\n", Min);
}
return ;
}
CF328A IQ Test
题意：是否为等差数列。
CF327E Axis Walking
题意：给定N个数字，现在要求给出一些排列使得这些排列的前缀和不等于给定的k个数，k最大为2。
分析：一开始想着进行搜索然后容斥，这样的做法会超时。动态规划的解法是设定dp[i], i 的具体数值我们不关心，我们只关心其二进制位的情况。dp[1010]表示放置第2和第4个数字并且暂时合理的方案数，于是可以列出动态规划方程: dp[1010] = dp[1000] + dp[0010].
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std; typedef long long LL;
const int N = (<<)+;
const int mod = int(1e9)+;
int n, m;
int a[], b[];
LL sum[N];
int f[N]; inline int lowbit(int x) {
return x & -x;
} int main() {
while (scanf("%d", &n) != EOF) {
memset(sum, , sizeof (sum));
memset(f, , sizeof (f));
for (int i = ; i < n; ++i) {
scanf("%d", &a[i]);
sum[<<i] = a[i];
}
scanf("%d", &m);
b[] = b[] = -;
for (int i = ; i < m; ++i) {
scanf("%d", &b[i]);
}
if (m == ) {
LL ret = ;
for (int i = ; i <= n; ++i) {
ret = (ret * i) % mod;
}
printf("%d\n", ret);
continue;
}
int LIM = << n;
f[] = ;
for (int i = ; i < LIM; ++i) {
sum[i] = sum[i-lowbit(i)] + sum[lowbit(i)];
if (sum[i] != b[] && sum[i] != b[]) {
LL tmp = ;
for (int j = i; j; j -= lowbit(j)) {
tmp += f[i-lowbit(j)];
}
f[i] = tmp % mod;
}
}
printf("%d\n", f[LIM-]);
}
return ;
}
CF327D Block Tower
分析：对每一个联通块，保证一个是B，其余均为R即可。
CF327C Magic Five
题意：给定一个字符串，要求删除一些字符后能够被5整除的数的数量。
分析：枚举以字符串中0和5的位置结束，若字符串从0开始，字符串长度为L，那么首项就是2^i，公比为2^L，项数就是题中所给定的数。先对首项求一个和，然后二分求出等比数列的和。
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std; typedef long long LL;
const int mod = int(1e9)+;
char str[];
int n, q; LL POW(LL a, int b) {
LL ret = ;
while (b) {
if (b & ) ret = (ret * a) % mod;
b >>= ;
a = (a * a) % mod;
}
return ret;
} LL cal(LL x, int b) { // 第x位为0或者是1
if (b == ) return x;
if (b & ) {
return (x*POW(q, b-)%mod + (+POW(q, b>>)) * cal(x, b>>)) % mod;
} else {
return ((+POW(q, b>>)) * cal(x, b>>)) % mod;
}
} int main() {
while (scanf("%s %d", str, &n) != EOF) {
int ft = , len = strlen(str);
q = POW(, len);
for (int i = ; i < len; ++i) {
if (str[i] == '' || str[i] == '') {
ft = (ft + POW(, i)) % mod;
}
}
printf("%d\n", cal(ft, n));
}
return ;
}
CF 327B Hungry Sequence
分析：筛选一遍素数套进去就可以了。
CF 327A Flipping Game
分析：直接枚举区间即可。
CF325E The Red Button
题意：给定一个数字N，现在每次只能够乘2模N或者乘2加1模N，问是否存在这样的环，使得以0开始，以0结束。
分析：目前尚不明白为什么从后往前按照先检查乘2加1的路径后检查乘2路径方法的正确性。
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <stack>
using namespace std; int N;
stack<int>stk;
char vis[]; int main() {
while (scanf("%d", &N) != EOF) {
if (N & ) {
puts("-1");
continue;
}
memset(vis, , sizeof (vis));
while (!stk.empty()) stk.pop();
stk.push(), stk.push(N/);
int x = N/;
while (x != ) {
int a = (x + N) >> , b = x >> ;
if (!vis[a]) {
x = a;
} else {
x = b;
}
stk.push(x);
vis[x] = ;
}
stk.push();
for (int i = ; !stk.empty(); ++i) {
printf(i == ? "%d" : " %d", stk.top());
stk.pop();
}
puts("");
}
return ;
}
CF325D Reclamation
CF325C Monsters and Diamonds
题意：有N个怪物，存在M中分裂方式，每种分裂方式指定一只怪物，该怪物每次分裂可以分裂成其他的怪物以及一些钻石，现在问每只怪物能够否分裂干净，如果分裂干净，那么分裂出的最少和最大的钻石数是多少？
分析：明确一定，一个怪物如果有分裂下限的话，那么才可能有分裂上限。在有分裂下限的情况下，还可能出现两种情况，一种是存在特定的分裂上限，一种是不存在上限，可以分裂出任意多的钻石。因此该计算过程应明确分为以下几个步骤：
1.使用一个优先队列维护好一个能够分裂干净的怪物集合，首先有输入数据能够读入一些怪物。
2.每次从这个优先队列中取出一个最小的分裂怪物，让这只怪物去更新分裂中包含该怪物的分裂方式，当某一分裂方式中的所有怪物都被确定能够分裂干净后，这个分裂方式就能够确定出一个最小钻石数了，然后再将这个怪物加入到优先队列中。
3.处理完下界后，如果没有下界的话，那么肯定就没有上界了，还有，如果有下界的话，那么肯定有一个上界。对于上界的求解需要用到搜索了。把能够分裂干净的边划到搜索的图中，如果成环的话，那么说明能够分裂出任意多的钻石，否则的话，求一个分裂中的最大值，所谓的上界值也就是从所有分裂方式中取出一个最大的。
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
using namespace std; struct Edge {
vector<int>v; // 存储捆绑分裂方式中的各个分裂目标
int size; // 存储该分裂方式中的目标数量
int d; // 存储通过该分裂方式能够得到的钻石数目
bool pass; // 该种分裂方式是否能够完全分解干净
Edge(const vector<int>&_v, int _size, int _d, bool _pass) : \
v(_v), size(_size), d(_d), pass(_pass) {}
}; const int N = ;
const int bound = ;
const int INF = 0x3f3f3f3f;
int m, n, high[N], low[N]; vector<Edge>eg[N];
vector<int>nd;
vector< pair<int,int> >p[N];
priority_queue< pair<int,int> >que; void init() {
for (int i = ; i <= n; ++i) {
eg[i].clear();
p[i].clear();
}
while (!que.empty()) que.pop();
memset(low, 0x3f, sizeof (low));
memset(high, 0x3f, sizeof (high));
} int dfs(int u) {
if (high[u] != INF) return high[u];
high[u] = -;
int res = ;
for (int i = ; i < eg[u].size(); ++i) {
if (!eg[u][i].pass) continue;
int sum = eg[u][i].d;
for (int j = ; j < eg[u][i].v.size(); ++j) {
int tmp = dfs(eg[u][i].v[j]);
if (tmp == -) return high[u] = -;
sum += tmp;
if (sum > bound) sum = bound;
}
if (sum > res) res = sum;
}
return high[u] = res;
} int main() {
while (scanf("%d %d", &m, &n) != EOF) {
init();
int x, y, c, d;
bool pass;
for (int i = ; i < m; ++i) {
scanf("%d %d", &x, &y);
pass = true, d = , nd.clear();
for (int j = ; j < y; ++j) {
scanf("%d", &c);
if (c == -) ++d;
else {
pass = false;
nd.push_back(c);
p[c].push_back(make_pair(x, eg[x].size()));
// p[c]确保c节点能够反向去更新某条分裂方式
}
}
eg[x].push_back(Edge(nd, nd.size(), d, pass));
if (pass && d < low[x]) {
low[x] = d;
que.push(make_pair(-d, x));
}
}
while (!que.empty()) {
int vertex = que.top().second, d = -que.top().first;
que.pop();
if (low[vertex] != d) {
continue;
}
for (int i = ; i < p[vertex].size(); ++i) { // 枚举包含该完全分解节点的分解方式
int parent = p[vertex][i].first, idx = p[vertex][i].second;
if (--eg[parent][idx].size == ) { // 说明该分解方式以全部找到完全分解的路径
int sum = eg[parent][idx].d;
eg[parent][idx].pass = true;
for (int j = ; j < eg[parent][idx].v.size(); ++j) {
sum += low[eg[parent][idx].v[j]];
if (sum > bound) sum = bound;
}
if (sum < low[parent]) {
low[parent] = sum;
que.push(make_pair(-sum, parent));
}
}
}
}
for (int i = ; i <= n; ++i) {
if (low[i] == INF) low[i] = -;
}
for (int i = ; i <= n; ++i) {
if (low[i] == -) high[i] = -;
else if (high[i] == INF) dfs(i);
}
for (int i = ; i <= n; ++i) {
printf("%d %d\n", low[i], high[i]);
}
}
return ;
}
CF325B Stadium and Games
题意：若有N个人要进行比赛，如果N为偶数，那么进行N/2场比赛，使得一半的被淘汰掉，如果剩下的人数仍然是偶数，那么继续这种操作，直到剩下的人数为奇数x时，进行x*(x-1)/2场比赛。现给定一个数M，问存在多少个人使得比赛的场次等于最后的这个数M。
分析：由题中给定的规则，可以推出，若在人数为p是等于一个奇数，那么最后的比赛场次将是：p^2 - (2^n - 3)p。由于数据范围的限制，n的取值将最多取到62，因此可以直接枚举n然后二分这个p。设二次函数为p^2 - (2^n - 3)p-2M，对称轴的取值最大为1，因此我们所求的正根就在1的右侧，这个性质非常好。在二分的时候也遇到了一些麻烦，前面直接将p,n代到式中进行计算，结果溢出了，处理的方法是判定p-(2^n-3)-2M/p这个式子的值，最后为0的p还需要判定是否为奇数以及是否被2M整除。
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; typedef long long LL;
// 存在等式 p^2 + (2^n-3)p - 2x = 0 const double eps = 1e-;
LL x, seq[], cnt; int sign(long double x) {
return x < -eps ? - : x > eps;
} void gao(int n) {
LL a = , b = (1LL << n)-, c = x << ;
LL l = , r = (LL)sqrt(1.0*c) + ;
while (l <= r) {
LL mid = (l + r) >> ;
LL ret = mid+b-c/mid;
if (ret > ) {
r = mid - ;
} else if (ret < ) {
l = mid + ;
} else {
if (mid & && c % mid == ) {
seq[cnt++] = (1LL<<(n-))*mid;
}
break;
}
}
} int main() {
while (scanf("%I64d", &x) != EOF) {
cnt = ;
for (int i = ; i < ; ++i) {
gao(i); // 枚举n
}
if (cnt == ) {
puts("-1");
continue;
}
sort(seq, seq+cnt);
for (int i = ; i < cnt; ++i) {
printf("%I64d\n", seq[i]);
}
}
return ;
}