这是在厚林工作室4个人打的一场

骚呢

两年没回去了

拿lzy的号打，打的被老刘查水表了

01

枚举$k^k$，$k\le 15$。 看到我的$T$就知道我是怎么wa的了。。

#include <bits/stdc++.h> using namespace std; typedef long long ll; ll powder(ll a,ll n){ if(n==0) return 1ll; ll ret = powder(a,n/2); ret = ret * ret; if(n&1) return ret*a; return ret; } int main(){ int T; ll n; while(cin>>n){ int cnt = 0; for(ll i=1;i<=15;i++){ if(powder(i,i)<=n) cnt++; } cout<<cnt<<endl; } return 0; }

#02 Color it

线段树，按y排，存x坐标，维护min

按x排存y坐标也行的，

防止炸空间，可以离散化或者像我这样，用到哪建到哪，最多是nlogn的

#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 1e6 + 7; bool getCol; struct segTree{ #define val(x) tree[x].val #define lson tree[rt].lc, l, m #define rson tree[rt].rc, m+1, r static const int TREE_N = N * 3 + 3e5; struct node{ int lc, rc, val; } tree[TREE_N]; int tot, root[55]; void build(){ memset(tree, 0, sizeof(tree)); memset(root, 0, sizeof(root)); tot = 0; } //p: pos, v: val void add(int p, int v, int &rt, int l, int r){ if (!rt) val(rt = ++tot) = v; val(rt) = min(val(rt), v); if (l == r) return; int m = (l + r) >> 1; if (p <= m) add(p, v, lson); else add(p, v, rson); } void query(int L, int R, int v, int rt, int l, int r){ if(getCol || !rt) return; if(L <= l && r <= R){ if(val(rt) <= v) getCol = 1; return; } int m = (l + r) >> 1; if (L <= m) query(L, R, v, lson); if (R > m) query(L, R, v, rson); } #undef val(x) #undef lson #undef rson } T; int main(){ //freopen("in.txt", "r", stdin); int op, x, y, c, L, R, X; T.build(); for (; scanf("%d", &op) && op != 3;){ if (op == 0) T.build(); else if(op == 1){ scanf("%d%d%d", &x, &y, &c); T.add(y, x, T.root[c], 1, N); }else if(op == 2){ scanf("%d%d%d", &X, &L, &R); int ans = 0; for(int i = 0; i <= 50; i++){ getCol = 0; T.query(L, R, X, T.root[i], 1, N); if (getCol) ans++; } printf("%d\n",ans); } } return 0; }

03

统计有多少$V=(A,B,C,D)$，$E=(AB,BC,CD,DA,AC)$。 考虑一个边作为对角线时，如果有K个点跟这个边的两个端点都相连，那么有${\text{C}}_K^2$中方案。 统计时，让条边记录在度数比较少的点处，减少枚举次数，每次将3个边一起算贡献。

#include <bits/stdc++.h> #define mp make_pair using namespace std; typedef long long ll; const int maxn = 100005; vector<pair<int,int> > e[maxn]; int du[maxn],u,v,n,m; ll cnt[maxn<<2]; struct node{ int u,v; }info[maxn<<2]; struct Node{ int idi,idep; Node(){} Node(int _idi,int _idep){ idi=_idi; idep=_idep; } }a[maxn<<2]; int main(){ while(~scanf("%d%d",&n,&m)){ for(int i=1;i<=n;i++) e[i].clear(); memset(a,0,sizeof a); memset(du,0,sizeof du); for(int i=1;i<=m;i++){ scanf("%d%d",&u,&v); du[u]++;du[v]++; info[i].u=u; info[i].v=v; } for(int i=1;i<=m;i++){ u=info[i].u;v=info[i].v; if(du[u] < du[v] || (du[u] == du[v] && u < v)) e[u].push_back(mp(v,i)); else e[v].push_back(mp(u,i)); } memset(cnt,0,sizeof cnt); for(int i=1;i<=m;i++){ u=info[i].u;v=info[i].v; for(auto ep:e[u]) a[ep.first]=Node(i,ep.second); for(auto ep:e[v]){ if(a[ep.first].idi==i){ cnt[i]++; cnt[ep.second]++; cnt[a[ep.first].idep]++; } } } ll res = 0; for(int i=1;i<=m;i++) res += (cnt[i]-1ll)*cnt[i]/2ll; printf("%lld\n",res); } return 0; }

04

Number of domino tilings of 4 X (n-1) board.

$a_n=a_{n-1}+5an-2+a_{n-3}-a_{n-4}$,直接用杜教板子。。

#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <string> #include <map> #include <set> #include <cassert> using namespace std; #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) typedef vector<int> VI; typedef long long ll; typedef pair<int,int> PII; const ll mod=1000000007; ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} // head int _; ll n; namespace linear_seq { const int N=10010; ll res[N],base[N],_c[N],_md[N]; vector<ll> Md; void mul(ll *a,ll *b,ll k) { rep(i,0,k+k) _c[i]=0; rep(i,0,k) if (a[i]) rep(j,0,k) _c[i+j]=(_c[i+j]+a[i]*b[j])%mod; for (int i=k+k-1;i>=k;i--) if (_c[i]) rep(j,0,SZ(Md)) _c[i-k+Md[j]]=(_c[i-k+Md[j]]-_c[i]*_md[Md[j]])%mod; rep(i,0,k) a[i]=_c[i]; } int solve(ll n,VI a,VI b) { ll ans=0,pnt=0; ll k=SZ(a); assert(SZ(a)==SZ(b)); rep(i,0,k) _md[k-1-i]=-a[i];_md[k]=1; Md.clear(); rep(i,0,k) if (_md[i]!=0) Md.push_back(i); rep(i,0,k) res[i]=base[i]=0; res[0]=1; while ((1ll<<pnt)<=n) pnt++; for (int p=pnt;p>=0;p--) { mul(res,res,k); if ((n>>p)&1) { for (int i=k-1;i>=0;i--) res[i+1]=res[i];res[0]=0; rep(j,0,SZ(Md)) res[Md[j]]=(res[Md[j]]-res[k]*_md[Md[j]])%mod; } } rep(i,0,k) ans=(ans+res[i]*b[i])%mod; if (ans<0) ans+=mod; return ans; } VI BM(VI s) { VI C(1,1),B(1,1); int L=0,m=1,b=1; rep(n,0,SZ(s)) { ll d=0; rep(i,0,L+1) d=(d+(ll)C[i]*s[n-i])%mod; if (d==0) ++m; else if (2*L<=n) { VI T=C; ll c=mod-d*powmod(b,mod-2)%mod; while (SZ(C)<SZ(B)+m) C.pb(0); rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod; L=n+1-L; B=T; b=d; m=1; } else { ll c=mod-d*powmod(b,mod-2)%mod; while (SZ(C)<SZ(B)+m) C.pb(0); rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod; ++m; } } return C; } int gao(VI a,ll n) { VI c=BM(a); c.erase(c.begin()); rep(i,0,SZ(c)) c[i]=(mod-c[i])%mod; return solve(n,c,VI(a.begin(),a.begin()+SZ(c))); } }; int main() { while(~scanf("%lld",&n)){ printf("%d\n",linear_seq::gao(VI{1,1, 5, 11, 36, 95, 281, 781, 2245, 6336, 18061, 51205, 145601, 413351, 1174500, 3335651, 9475901, 26915305, 76455961, 217172736},n)); } }

05

求三种sum丢掉第k位

预处理出所有的前缀和后缀

黑康说：按位枚举？？？

#include <cstdio> #include <iostream> using namespace std; const int N = 1e5 + 7; int arr[N]; int prXor[N], prAnd[N], preOr[N]; int suXor[N], suAnd[N], sufOr[N]; int main(){ //freopen("in.txt", "r", stdin); int n, q; for (; ~scanf("%d%d", &n, &q);){ prXor[0] = suXor[n+1] = 0; prAnd[0] = suAnd[n+1] = ~0; preOr[0] = sufOr[n+1] = 0; //printf("%d\n", prAnd[0]); for (int i = 1; i <= n; i++){ scanf("%d", &arr[i]); prXor[i] = prXor[i-1] ^ arr[i]; prAnd[i] = prAnd[i-1] & arr[i]; preOr[i] = preOr[i-1] | arr[i]; } for (int i = n; i >= 1; i--){ suXor[i] = suXor[i+1] ^ arr[i]; suAnd[i] = suAnd[i+1] & arr[i]; sufOr[i] = sufOr[i+1] | arr[i]; } for (int k; q--;){ scanf("%d", &k); int ansXor = prXor[k-1] ^ suXor[k+1]; int ansAnd = prAnd[k-1] & suAnd[k+1]; int ansOrr = preOr[k-1] | sufOr[k+1]; printf("%d %d %d\n", ansAnd, ansOrr, ansXor); } } return 0; }

06

好像是个傻逼题，然后犯了傻逼错误

贡献了-6的罚时，

国王的坐标给的那么恶心的数字，就是告诉你，国王不会在wall上，然后要让国王能到达任意地方，就要让这些wall无法形成环就可以了，所以，不是环，树嘛，要求删去的最少，求个最大生成树，然后$ans=su{m}_{all}-su{m}_{tree}$，

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define fi first #define se second using namespace std; typedef pair<int, int> P; const int N = 1e5 + 7; struct Edge{ int from,to,w; Edge(){} Edge(int x,int y,int z):from(x),to(y),w(z){} bool operator < (const Edge& a) const{return w > a.w;} } edges[N * 2]; int f[N]; int F(int x){return f[x]==x ? x : (f[x]=F(f[x]));} bool vis[N]; P kruskal(int n, int m){ int treenum = n; //forests for (int i = 1;i <= n; i++) f[i] = i; sort(edges, edges + m); int cnt = 0, ans = 0; for (int i = 0; i < m; i++){ Edge &e = edges[i]; if (F(e.from) == F(e.to)) continue; f[F(e.from)] = F(e.to); treenum--; ans += e.w; } return P(treenum, ans); } int main(){ //freopen("in.txt", "r", stdin); int n, x, y, u, v, c, m; for (; scanf("%d%d", &n, &m)==2;){ for (int i = 1; i <= n; i++) scanf("%d%d", &x, &y); int all = 0; for (int i = 0; i < m; i++){ scanf("%d%d%d", &u, &v, &c); edges[i] = Edge(u, v, c); all += c; } P p = kruskal(n, m); printf("%d %d\n", m-(n-p.fi), all - p.se); } return 0; }

07毛对子和毛顺子

贪心：取i，i-1,i-2这个顺子的时候先把i-1，i-2的对子取掉，取完再取i的对子

#include <bits/stdc++.h> using namespace std; int a[1000005],x,n; int main(){ while(~scanf("%d",&n)){ memset(a,0,sizeof a); for(int i=1;i<=n;i++){ scanf("%d",&x); a[x]++; } int cnt = 0; for(int i=1;i<=1000000;i++){ if(i>=3) if(a[i] && a[i-1] && a[i-2]){ a[i]--;a[i-1]--;a[i-2]--; cnt++; } cnt += a[i]/2; a[i] %= 2; } printf("%d\n",cnt); } return 0; }

08

开始打表的时候发现如果a是奇数的时候肯定是1

然后a是偶数的时候，2的因子个数很多，枚举一下就行了，后面的就为0了。

开始打表发现，$a\ge n$的时候，几乎是所有的偶数，无脑了几发。发现$a<n$的时候答案不对。事实上，枚举一下较小的部分。加上后面0的部分。

#include <bits/stdc++.h> using namespace std; typedef long long ll; ll n,a; ll power(ll a,ll b,ll mod){ if(b==0) return 1ll; ll ret = power(a,b/2,mod); ret = ret * ret % mod; if(b&1) return ret*a%mod; return ret; } ll up(ll n,ll a){ return (n + a - 1) / a; } int main(){ //freopen("output.txt","w",stdout); while(~scanf("%lld%lld",&n,&a)){ if(a&1){ puts("1"); continue; } ll mod = 1ll<<n; ll res = 0; for(int i=2;i<=n;i+=2) if(power(a,i,mod) == power(i,a,mod)) res++; res += (1<<n) >> (up(n,a)); res -= n >> (up(n,a)); printf("%d\n",res); } return 0; }

#10

【bzoj3261】最大异或和 首先，如果是区间异或的话，可以用可持续化Trie树。对于树上的可以用dfs序做。查询就查询in[u]到out[u]的的区间就行了。

#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> #include<cstring> #define ll long long #define N 200005 #define inf 2000000000 using namespace std; 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*10+ch-'0';ch=getchar();} return x*f; } int bin[30]; int n,m; int a[N],b[N],root[N]; struct trie{ int cnt; int ch[N*30][2],sum[N*30]; void init(){ cnt = 0; memset(ch,0,sizeof ch); memset(sum,0,sizeof sum); } int insert(int x,int val){ int tmp,y;tmp=y=++cnt; for(int i=29;i>=0;i--) { ch[y][0]=ch[x][0];ch[y][1]=ch[x][1]; sum[y]=sum[x]+1; int t=val&bin[i];t>>=i; x=ch[x][t]; ch[y][t]=++cnt; y=ch[y][t]; } sum[y]=sum[x]+1; return tmp; } int query(int l,int r,int val){ int tmp=0; for(int i=29;i>=0;i--) { int t=val&bin[i];t>>=i; if(sum[ch[r][t^1]]-sum[ch[l][t^1]]) tmp+=bin[i],r=ch[r][t^1],l=ch[l][t^1]; else r=ch[r][t],l=ch[l][t]; } return tmp; } }trie; int in[N],out[N],cnt; vector<int> e[N]; void dfs(int id,int fa){ in[id] = ++cnt; root[cnt] = trie.insert(root[cnt-1],a[id]); for(auto ep:e[id]){ if(ep == fa) continue; dfs(ep,id); } out[id]=cnt; } int main(){ bin[0]=1;for(int i=1;i<=30;i++)bin[i]=bin[i-1]<<1; while(~scanf("%d%d",&n,&m)){ for(int i=1;i<=n;i++) e[i].clear(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=2;i<=n;i++){ int v; scanf("%d",&v); e[v].push_back(i); } cnt=0; trie.init(); dfs(1,0); int u,x; //for(int i=1;i<=n;i++){ // printf("in[%d],out[%d] %d\n",in[i],out[i],i); //} //cout<<root[4]<<endl; while(m--){ scanf("%d%d",&u,&x); printf("%d\n",trie.query(root[in[u]-1],root[out[u]],x)); } } return 0; }

哇哦