体活就是用来上体育的~~~Cat到操场上跑了n圈，6:00~6:25，并且边跑边唱歌，就是那首我最喜欢的"世界问，你是谁，来自哪……"好像路上有人因此回头多看了两眼，今天的云好美，一路上的老师有好多在拍照的，仰望天空不知道Dream是近在咫尺还是远在天涯……好久没有这样放纵了呢……
A. 欧几里得的噩梦
建个图，把x和y连边（没有y就建一个虚点m+1，把x和m+1连边），这个图不能成环，用并查集判一下环。意思就是要把能用小数异或得到的值删掉，如果有一个a,b是1的数，还有一个b,c是1的数，还有一个c,d是1的数，可以得到a,d，再来一个a,d是1的数就可以把它去掉了，方案数就是2^被选上的数的个数。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e5 + 2;
const int N = 1e5 + 2;
const ll mod = 1e9 + 7;
int n, m, fa[maxn], nns;
bool del[maxn];
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
{
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
int find(int x)
{
if(x == fa[x]) return x;
return fa[x] = find(fa[x]);
}
ll qpow(ll a, ll b)
{
ll ans = 1;
while(b)
{
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
int main()
{
n = read(); m = read();
for(int i=1; i<=m+1; i++) fa[i] = i;
for(int i=1; i<=n; i++)
{
int tp = read();
if(tp == 1)
{
int x = read();
int fx = find(x), fy = find(m+1);
//printf("fx = %d fy = %d\n", fx, fy);
if(fx == fy) nns++, del[i] = 1;
else fa[fx] = fy;
}
else
{
int x = read(), y = read();
int fx = find(x), fy = find(y);
//printf("fx = %d fy = %d\n", fx, fy);
if(fx == fy) nns++, del[i] = 1;//fx == fx 不交个0分改不了低错是吗！？
else fa[fx] = fy;
}
}
printf("%lld %d\n", qpow(2, n-nns), n-nns);
for(int i=1; i<=n; i++)
{
if(!del[i]) printf("%d ", i);
}
return 0;
}
B. 清扫
树上两点间最短路径是确定的，可以由每个点的值推出(这个点和父节点相连的边)每条边要覆盖的次数，和叶子节点相连的所有边权和就是点权，和非叶子节点相连的所有边权和是点权的2倍，因为要从这个点的两侧任选叶子把它的点权消掉，每消一个点权花费两条边。
于是上面的操作把只有叶子之间可以相互消的问题转到了任意的点上，就可以从下到上地判断合法了。判断合法有3个限制条件：(设这个点的孩子权值和为sum)
1.sum>=a[u]，这些sum可以相互消，这样两个孩子对应a[u]-1，也可以连出去，这样一个孩子使a[u]-1，如果不满足这个条件表示所有sum都向外消都无法使a[u]变成0.
2.sum<=a[u]*2，如果不满足这个条件表示所有sum都内部消也能使a[u]提前消为0.
3.最大的孩子的权值小于等于a[u]，否则这个孩子消不掉了。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 3;
const ll mod = 1e9 + 7;
int n, m, du[maxn], rt;
ll a[maxn];
vector<int> son[maxn];
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
{
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
void dfs(int u, int fa)
{
if(du[u] == 1) return;
ll sum = 0, mx = 0;
for(int i=0; i<son[u].size(); i++)
{
int v = son[u][i];
if(v == fa) continue;
dfs(v, u);
sum += a[v];
mx = max(mx, a[v]);
}
if(sum < a[u] || sum > 2*a[u]) printf("NO\n"), exit(0);
if(mx > a[u]) printf("NO\n"), exit(0);
a[u] = 2 * a[u] - sum;
}
int main()
{
n = read();
for(int i=1; i<=n; i++) a[i] = read();
if(n == 2)
{
if(a[1] != a[2]) printf("NO\n");
else printf("YES\n");
exit(0);
}
for(int i=1; i<n; i++)
{
int x = read(), y = read();
son[x].push_back(y); son[y].push_back(x);
du[x]++; du[y]++;
}
int rt = 1;
for( ;du[rt]==1; rt++);
dfs(rt, 0);
if(!a[rt]) printf("YES\n");
else printf("NO\n");
return 0;
}
C. 购物
用类似背包dp的东西结合二进制数枚举乱搞一波……本来打算用线段树来搞区间覆盖，后来忽然发现计算出可以搭配的每一个值按从小到大的顺序枚举就可以直接加上它的范围：(表示向上取整)(a+1)/2~a
code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e6 + 2;
const int N = 1e5 + 2;
const ll mod = 1e9 + 7;
int n, a[N], sum, Max, ans;
bool f[maxn];
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
{
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
/*
struct Segmenttree
{
struct node
{
int sum, lazy;
}t[maxn<<2];
void pushup(int x)
{
t[x].sum = t[x<<1].sum + t[x<<1|1].sum;
}
void pushdown(int x, int l, int r, int mid)
{
int ls = x<<1, rs = x<<1|1;
t[ls].lazy = t[rs].lazy = 1;
t[ls].sum = mid-l+1;
t[rs].sum = r-mid;
t[x].lazy = 0;
}
void update(int x, int l, int r, int L, int R)
{
if(L <= l && r <= R)
{
t[x].sum = r-l+1;
t[x].lazy = 1;
return;
}
int mid = (l + r) >> 1;
if(t[x].lazy) pushdown(x, l, r, mid);
if(L <= mid) update(x<<1, l, mid, L, R);
if(R > mid) update(x<<1|1, l, mid, L, R);
pushup(x);
}
int query(int x, int l, int r, int L, int R)
{
if(L <= l && r <= R)
{
return t[x].sum;
}
int mid = (l + r) >> 1, ans = 0;
if(t[x].lazy) pushdown(x, l, r, mid);
if(L <= mid) ans += query(x<<1, l, mid, L, R);
if(R > mid) ans += query(x<<1|1, mid+1, r, L, R);
return ans;
}
}T;
*/
set<ll> s;
ll res;
inline void check(int num)
{
ll sum = 0;
for(int i=1; i<=n; i++)
{
if(num & (1<<(i-1))) sum += a[i];
}
s.insert(sum);
}
int main()
{
n = read();
if(n <= 3)
{
for(int i=1; i<=n; i++) a[i] = read();
Max = 1 << n;
for(int i=1; i<Max; i++)
{
check(i);
}
ll las = 0;
for(ll x : s)
{
ll mi = max((x+1)/2, las+1);
//printf("mi = %lld x = %lld\n", mi, x);
res += x - mi + 1;
las = x;
}
printf("%lld\n", res);
exit(0);
}
for(int i=1; i<=n; i++)
{
a[i] = read(); sum += a[i];
}
f[0] = 1;
for(int i=1; i<=n; i++)
{
for(int j=sum; j>=a[i]; j--)
{
f[j] |= f[j-a[i]];
}
}
int las = 0;
for(int i=1; i<=sum; i++)
{
if(f[i])
{
int mi = max((i+1)/2, las+1);
ans += i - mi + 1;
//printf("mi = %d i = %d\n", mi, i);
las = i;
//Min = (i+1)/2;
//Max = i;
//T.update(1, 1, sum, Min, Max);
}
}
//ans = T.query(1, 1, sum, 1, sum);
printf("%d\n", ans);
return 0;
}
但是没有想到每个数的范围其实是(a+1)/2~suma，suma代表排序后到1的前缀和，就是我们根本不用去找它们可以组成哪些数，我们只需要边界就够了。
suma一定是前(啊临时假设到i了吧)i个数能组成的最大值，(a+1)/2一定是新保证加入第i个数来配凑可得的最小值，中间的值产生的区间一定被包含在这个区间范围内并且没有空余。假设a[i]和a[i-1]凑在一起组成了新数，它除以二向下取整一定会大于(a[i]+1)/2，并且由于a[i-1]<a[i]，a[i-1]/2 < a[i]/2，(a[i]+a[i-1])/2 < a[i]，左端点使得覆盖范围联通，右端点使得覆盖范围拓展。以此类推得到一个大数和一个小数组合产生的区间都像这样。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e6 + 2;
const int N = 1e5 + 2;
const ll mod = 1e9 + 7;
int n;
ll a[maxn], sum[maxn], ans;
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
{
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
int main()
{
n = read();
for(int i=1; i<=n; i++) a[i] = read();
sort(a+1, a+1+n);
for(int i=1; i<=n; i++)
{
sum[i] = sum[i-1] + a[i];
}
for(int i=1; i<=n; i++)
{
ll mi = max(sum[i-1]+1, (a[i]+1)/2);
//printf("%lld %lld\n", mi, sum[i]);
ans += sum[i] - mi + 1;
}
printf("%lld\n", ans);
return 0;
}
D. ants
permu这个题我还做过，然而忘了，Cat不叫Cat了，干脆叫狗熊啃玉米好了……虽然当时那个线段树并不是正解，但是50-20=30……
所以就去鹤了一下题解(并查集版本的，似乎有别的做法更快)，大概回滚莫队的原理是整个代码最不好理解的东西了：因为删除或插入中的某一项过于复杂，于是就只保留一个，在这个题里是只有增加，对于同一范围内有序的项增加，无序的项增加无效需要删除影响，范围都改了那就直接全部清空就行。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 2;
const int N = 1e5 + 2;
const ll mod = 1e9 + 7;
int n, m, siz[maxn], fa[maxn], stk[maxn], res, top, a[maxn], ans[maxn], t;
bool vis[maxn];
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
{
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
struct node
{
int l, r, pos, id;
bool operator < (const node &T) const
{
return pos == T.pos ? r < T.r : pos < T.pos;
}
}q[maxn];
int find(int x)
{
return x == fa[x] ? x : find(fa[x]);//没有路径压缩！我真手欠！
}
void merge(int x, int y)
{
x = find(x), y = find(y);
if(x == y) return;
if(siz[x] > siz[y]) swap(x, y);
fa[x] = y;
siz[y] += siz[x];
stk[++stk[0]] = x;
}
void add(int x)
{
vis[x] = 1;
if(vis[x-1]) merge(x, x-1);
if(vis[x+1]) merge(x, x+1);
res = max(res, siz[find(x)]);
}
void del()
{
while(stk[0] > top)
{
siz[find(stk[stk[0]])] -= siz[stk[stk[0]]];
fa[stk[stk[0]]] = stk[stk[0]];
stk[0]--;
}
}
int main()
{
n = read(); m = read();
t = sqrt(n);
for(int i=1; i<=n; i++) a[i] = read();
for(int i=1; i<=m; i++)
{
q[i].l = read(); q[i].r = read();
q[i].pos = (q[i].l-1)/t+1;
q[i].id = i;
}
sort(q+1, q+m+1);
int l, r, pos;
for(int i=1; i<=m; i++)
{
if(q[i].pos != q[i-1].pos)
{
for(int j=1; j<=n; j++)
{
fa[j] = j; vis[j] = 0; siz[j] = 1;
}
res = stk[0] = 0;
l = pos = q[i].pos*t+1;
r = l-1;
}
if(q[i].pos == (q[i].r-1)/t+1)
{
int now = 1, len = 1;
for(int j=q[i].l; j<=q[i].r; j++) stk[++stk[0]] = a[j];
sort(stk+1, stk+stk[0]+1);
for(int j=1; j<=stk[0]; j++)
{
if(stk[j] == stk[j-1]+1 && j>1) now++;
else now = 1;
len = max(len, now);
}
ans[q[i].id] = len;
stk[0] = 0;
}
else
{
while(r < q[i].r) add(a[++r]);
int flag = res;
top = stk[0];
while(l > q[i].l) add(a[--l]);
ans[q[i].id] = res;
res = flag;
while(l < pos) vis[a[l++]] = 0;
del();
}
}
for(int i=1; i<=m; i++) printf("%d\n", ans[i]);
return 0;
}
标签：10,ch,const,int,ll,stk,maxn,CSP,模拟 From： https://www.cnblogs.com/Catherine2006/p/16726334.html