咕值详见去年多校
牛客
题号 | 标题 | 团队的状态 |
---|---|---|
A | Equivalent Prefixes | 通过 |
B | Integration | 通过 |
C | Euclidean Distance | 通过 |
D | Parity of Tuples | 未通过 |
E | ABBA | 通过 |
F | Random Point in Triangle | 通过 |
G | Substrings 2 | 未通过 |
H | XOR | 通过 |
I | Points Division | 通过 |
J | Fraction Comparision | 通过 |
A
思路:二分+单调栈
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define y1 y11 #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb emplace_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pli pair<LL, int> #define pii pair<int, int> #define piii pair<pii, int> #define pdd pair<double, double> #define mem(a, b) memset(a, b, sizeof(a)) #define debug(x) cerr << #x << " = " << x << " "; #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); //head const int N = 1e5 + 5; int n, a[N], b[N], la[N], ra[N],lb[N], rb[N]; stack<int> st; inline bool ck(int m) { while(!st.empty()) st.pop(); st.push(0); for (int i = 1; i <= m; ++i) { while(!st.size() > 1 && a[st.top()] > a[i]) st.pop(); la[i] = st.top(); st.push(i); } while(!st.empty()) st.pop(); st.push(m+1); for (int i = m; i >= 1; --i) { while(st.size() > 1 && a[st.top()] > a[i]) st.pop(); ra[i] = st.top(); st.push(i); } while(!st.empty()) st.pop(); st.push(0); for (int i = 1; i <= m; ++i) { while(!st.size() > 1 && b[st.top()] > b[i]) st.pop(); lb[i] = st.top(); st.push(i); } while(!st.empty()) st.pop(); st.push(m+1); for (int i = m; i >= 1; --i) { while(st.size() > 1 && b[st.top()] > b[i]) st.pop(); rb[i] = st.top(); st.push(i); } for (int i = 1; i <= m; ++i) if(la[i] != lb[i] || ra[i] != rb[i]) return false; return true; } int main() { while(~scanf("%d", &n)) { for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); for (int i = 1; i <= n; ++i) scanf("%d", &b[i]); int l = 1, r = n, m = l+r+1 >>1; while( l < r) { if(ck(m)) l = m; else r = m-1; m = l+r+1>>1; } printf("%d ", m); } return 0; }
B
思路:裂项,详见D神博客
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define y1 y11 #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb push_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pli pair<LL, int> #define pii pair<int, int> #define piii pair<pii, int> #define pdd pair<double, double> #define mem(a, b) memset(a, b, sizeof(a)) #define debug(x) cerr << #x << " = " << x << " "; #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); //head const int N = 1e3 + 5; const int MOD = 1e9 + 7; int a[N], n; LL q_pow(LL n, LL k) { LL ans = 1; while(k){ if(k&1) ans = (ans * n) % MOD; n =(n * n) % MOD; k >>= 1; } return ans; } int main() { while(~scanf("%d", &n)) { for (int i = 1; i <= n; ++i) scanf("%d",&a[i]); LL ans = 0; for (int i = 1; i <= n; ++i) { LL tmp = 2*a[i]%MOD; for (int j = 1; j <= n; ++j) { if(i == j) continue; tmp = (tmp * (a[j]*1LL*a[j]%MOD-a[i]*1LL*a[i]%MOD))%MOD; } ans = (ans + q_pow(tmp, MOD-2))%MOD; } printf("%lld ", (ans+MOD)%MOD); } return 0; }
C
思路:贪心,从大到小推平。详见大佬博客
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define y1 y11 #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb push_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pli pair<LL, int> #define pii pair<int, int> #define piii pair<pii, int> #define pdd pair<double, double> #define mem(a, b) memset(a, b, sizeof(a)) #define debug(x) cerr << #x << " = " << x << " "; #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); //head const int N = 1e4 + 5; int a[N], sum[N], n, m; int main() { while(~scanf("%d %d", &n, &m)) { for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); sort(a+1, a+1+n, greater<int>()); for (int i = 1; i <= n; ++i) sum[i] = sum[i-1]+a[i]; int pos = n+1; LL x=0, y=0; for (int i = 1; i <= n; ++i){ if(sum[i]-a[i]*i <= m) { x = (sum[i]-m)*1LL*(sum[i]-m)*i; y = i*i; } else { pos = i; break; } } for (int i = pos; i <= n; ++i) x += a[i]*1LL*a[i]*y; y *= m*m; LL d = __gcd(x, y); if(d) x /= d, y /= d; if(x == 0) printf("0 "); else if(y == 1) printf("%lld ", x); else printf("%lld/%lld ", x, y); } return 0; }
D
E
思路:dp,保证A和B的差值在$-m$到$+n$之间
代码:
#include <bits/stdc++.h> using namespace std; #define pb push_back #define fi first #define se second #define debug(x) cerr<<#x << " := " << x << endl; #define bug cerr<<"-----------------------"<<endl; #define FOR(a, b, c) for(int a = b; a <= c; ++ a) typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; template<class T> void _R(T &x) { cin >> x; } void _R(int &x) { scanf("%d", &x); } void _R(ll &x) { scanf("%lld", &x); } void _R(double &x) { scanf("%lf", &x); } void _R(char &x) { scanf(" %c", &x); } void _R(char *x) { scanf("%s", x); } void R() {} template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); } template<typename T> inline T read(T&x){ x=0;int f=0;char ch=getchar(); while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x=f?-x:x; } const int inf = 0x3f3f3f3f; const int mod = 1e9+7; /**********showtime************/ const int maxn = 8e3+9; ll dp[maxn][maxn]; int g(int x) { return x + 4000; } int main(){ int n,m; while(~scanf("%d%d", &n, &m)) { int s = 2 * (n + m); int t = (n + m); for(int i=0; i<=s; i++) { for(int j=-t; j<=t; j++) { dp[i][g(j)] = 0; } } dp[0][g(0)] = 1; for(int i=1; i<=s; i++) { for(int j=-t; j<=t; j++) { if(j <= n) dp[i][g(j)] = (dp[i][g(j)] + dp[i-1][g(j-1)] ) %mod; if(j >= -m) dp[i][g(j)] = (dp[i][g(j)] + dp[i-1][g(j+1)] ) %mod; } } // cout<<dp[s][g(0)]<<endl; printf("%lld ", dp[s][g(0)]); } return 0; }
F
思路:
$frac{22*s}{36}$
代码:
#include<bits/stdc++.h> #define ll long long using namespace std; struct Point { // double pan duan ll x,y; Point(ll a=0,ll b=0) { x=a;y=b; }; }; typedef Point Vector; Vector operator + (Vector A, Vector B){ return Vector(A.x+B.x, A.y+B.y); } // 向量相加 Vector operator - (Point A, Point B){ return Vector(A.x-B.x, A.y-B.y); } // 向量生成 double operator * (Vector A, Vector B){ return A.x*B.x-A.y*B.y; } // 点积 double operator ^ (Vector A, Vector B){ return A.x*B.y-A.y*B.x; } // 叉积 ll Cross(Vector A, Vector B) { return A.x*B.y - A.y*B.x; } // 叉积 ll Area2(Point A, Point B, Point C) { return Cross(B-A, C-A); } // 四边形面积 int main(){ Point a,b,c; while(~scanf("%lld %lld %lld %lld %lld %lld",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y)){ ll area=abs(Cross(b-a,c-a) ) *11; printf("%lld ",area); } }
G
H
思路:线性基。
先将问题转换成包含某个元素的异或起来为0的集合个数和
首先,先选出一组基(假设大小为$r$),那么对于非基元素的任意组合都可由基线性表示,也就是说对于每个非基元素,有$2^{n-r-1}$个包含它的集合满足题意,
这部分贡献是$(n-r)*2^{n-r-1}$。
然后考虑包含基元素的满足题意的集合个数,对于某个基元素,将剩下的$n-1$个元素构成一组基,看能不能线性表示出它,如果能,包含这个基元素的集合个数是$2^{剩下元素个数}$
对于第二种情况可以先处理出非基元素的一组基。
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define y1 y11 #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb push_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pli pair<LL, int> #define pii pair<int, int> #define piii pair<pii, int> #define pdd pair<double, double> #define mem(a, b) memset(a, b, sizeof(a)) #define debug(x) cerr << #x << " = " << x << " "; #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); //head const int N = 1e5 + 5; const int MOD = 1e9 + 7; int n; LL a[N]; vector<LL> s, b, other, B; LL q_pow(LL n, LL k) { if(k < 0) return 0; LL res = 1; while(k) { if(k&1) res = (res*n)%MOD; n = (n*n)%MOD; k >>= 1; } return res; } int main() { while(~scanf("%d", &n)) { s.clear();b.clear();other.clear();B.clear(); for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]); for (int i = 1; i <= n; ++i) { LL t = a[i]; for (LL x : b) { if((t^x) < t) t ^= x; } if(t) b.pb(t), s.pb(a[i]); else other.pb(a[i]); } int sz = b.size(); LL ans = (n-sz)*q_pow(2, n-sz-1)%MOD; for (LL x : other) { for (LL t : B) { if((x^t) < x) x ^= t; } if(x) B.pb(x); } for (LL x : s) { vector<LL> tb = B; for (LL t : s) { if(t != x) { for (LL y : tb) { if((y^t) < t) t ^= y; } if(t) tb.pb(t); } } for (LL t : tb) { if((x^t) < x) x ^= t; } if(!x) ans = (ans + q_pow(2, n-tb.size()-1))%MOD; } printf("%lld ", ans); } return 0; }
I
思路:线段树优化dp。
首先根据题意,A和B集合的分界线肯定是一横一竖交替出现的折线。那么考虑以每个点i为折线的转折点时的dp[i]。用线段树维护之前转折点的最大值并更新以当前点为转折点的最大值。
对于每个点i,它对y值为[0, a[i].y-1]转折点的贡献为a,对y值为[a[i].y+1,len]转折点的贡献为b。因为a集合在上,b集合在下。
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define y1 y11 #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb emplace_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pli pair<LL, int> #define pii pair<int, int> #define piii pair<pii, int> #define pdd pair<double, double> #define mem(a, b) memset(a, b, sizeof(a)) #define debug(x) cerr << #x << " = " << x << " "; #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); //head const int N = 1e5 + 5; struct Node { int x, y, a, b; bool operator < (const Node & rhs) const { if(x == rhs.x) return y > rhs.y; else return x < rhs.x; } }a[N]; int n; vector<int> vc; LL mx[N<<2], lazy[N<<2]; inline void push_up(int rt) { mx[rt] = max(mx[rt<<1], mx[rt<<1|1]); } inline void push_down(int rt) { lazy[rt<<1] += lazy[rt]; lazy[rt<<1|1] += lazy[rt]; mx[rt<<1] += lazy[rt]; mx[rt<<1|1] += lazy[rt]; lazy[rt] = 0; } void build(int rt, int l, int r) { mx[rt] = lazy[rt] = 0; if(l == r) return ; int m = l+r >> 1; build(ls); build(rs); push_up(rt); } void update(int p, LL v, int rt, int l, int r) { if(l == r){ mx[rt] = v; return ; } int m = l+r >> 1; if(lazy[rt]) push_down(rt); if(p <= m) update(p, v, ls); else update(p, v, rs); push_up(rt); } void Update(int L, int R, int v, int rt, int l, int r) { if(L > R) return ; if(L <= l && r <= R) { mx[rt] += v; lazy[rt] += v; return ; } int m = l+r >> 1; if(lazy[rt]) push_down(rt); if(L <= m) Update(L, R, v, ls); if(R > m) Update(L, R, v, rs); push_up(rt); } LL query(int L, int R, int rt, int l, int r){ if(L > R) return 0; if(L <= l && r <= R) return mx[rt]; int m = l+r >> 1; if(lazy[rt]) push_down(rt); LL ans = 0; if(L <= m) ans = max(ans, query(L, R, ls)); if(R > m) ans = max(ans, query(L, R, rs)); push_up(rt); return ans; } int main() { while(~scanf("%d", &n)) { vc.clear(); for (int i = 1; i <= n; ++i) scanf("%d %d %d %d",&a[i].x, &a[i].y, &a[i].a, &a[i].b), vc.pb(a[i].y); sort(vc.begin(), vc.end()); vc.erase(unique(vc.begin(), vc.end()), vc.end()); for (int i = 1; i <= n; ++i) a[i].y = lower_bound(vc.begin(), vc.end(), a[i].y)-vc.begin()+1; sort(a+1, a+1+n); int l = vc.size(); ++l; build(1, 0, l); for (int i = 1; i <= n; ++i) { LL tmp = query(0, a[i].y, 1, 0, l); update(a[i].y, tmp+a[i].b, 1, 0, l); Update(0, a[i].y-1, a[i].a, 1, 0, l); Update(a[i].y+1, l, a[i].b, 1, 0, l); } printf("%lld ", mx[1]); } return 0; } /* 3 1 1 10 1 8 9 10 1 5 4 10 1 */
J
思路:大数过
import java.math.BigInteger; import java.util.*; public class Main { /** * @param args */ public static void main(String[] args) { BigInteger x, a, y, b; Scanner reader = new Scanner(System.in); while(reader.hasNext()) { x = reader.nextBigInteger(); a = reader.nextBigInteger(); y = reader.nextBigInteger(); b = reader.nextBigInteger(); if(x.multiply(b).compareTo(y.multiply(a)) == 0) { System.out.println("="); } else if(x.multiply(b).compareTo(y.multiply(a)) > 0) { System.out.println(">"); } else { System.out.println("<"); } } } }
题号 | 标题 | 团队的状态 |
---|---|---|
A | Eddy Walker | 通过 |
B | Eddy Walker 2 | 通过 |
C | Go on Strike! | 未通过 |
D | Kth Minimum Clique | 通过 |
E | MAZE | 通过 |
F | Partition problem | 通过 |
G | Polygons | 通过 |
H | Second Large Rectangle | 通过 |
I | Inside A Rectangle | 未通过 |
J | Subarray | 通过 |
A
思路:蒙特卡洛一下,就能找到规律,除了0这个点,其他点的概率是$frac{1}{n-1}$,队友读了题居然没跟我说题意,血亏。
以n=10为例,打表代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back int a[10]; int main() { mt19937 mt_rand(time(NULL)); for (int i = 1; i <= 100000; ++i) { int st = 0; int up = 1<<10, s = 1; while(true) { if(mt_rand()%2 == 0) st = (st+9)%10; else st = (st+1)%10; s |= 1<< st; if(s == up-1) { a[st]++; break; } } } for (int i = 0; i < 10; ++i) printf("%d %.10f ", i, a[i]*1.0/100000); return 0; }
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define LL long long #define pb push_back const int MOD = 1e9 + 7; int T, m, n; LL q_pow(LL n, LL k) { LL res = 1; while(k) { if(k&1) res = (res*n) % MOD; n = (n * n)%MOD; k >>= 1; } return res; } int main() { scanf("%d", &T); LL res = 1; while(T--) { scanf("%d %d", &n, &m); if(n == 1) ; else if(m) (res *= q_pow(n-1, MOD-2)) %= MOD; else res *= 0; printf("%lld ", res); } return 0; }
B
思路:容易发现是个线性递推式,因为系数$frac{1}{k}$是个常数。于是可以打出前2*k项,扔进杜教BM板子里就能求出第$n$项。
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back const int mod = 1e9 + 7; const int MOD = 1e9 + 7; ll q_pow(ll n, ll k) { ll res = 1; while(k) { if(k&1) res = (res*n)%mod; n = (n*n)%mod; k >>= 1; } return res; } namespace linear_seq { const int N=10010; #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 mp make_pair #define all(x) (x).begin(),(x).end() #define SZ(x) ((int)(x).size()) typedef vector<ll> VI; typedef pair<ll,ll> PII; 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;} ll res[N],base[N],_c[N],_md[N]; vector<ll> Md; void mul(ll *a,ll *b,int 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]; } ll solve(ll n,VI a,VI b) { // a 系数 b 初值 b[n+1]=a[0]*b[n]+... // printf("%d ",SZ(b)); ll ans=0,pnt=0; int 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; } ll 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 k, T; ll n; int main() { scanf("%d", &T); while(T--) { scanf("%d %lld", &k, &n); vector<ll> vc; if(n == -1) printf("%lld ", 2*q_pow(k+1, MOD-2)%MOD); else { vc.pb(1); for (int i = 1; i <= 2*k; ++i) { ll tmp = 0; for (int j = max(0, i-k); j < i; ++j){ (tmp += vc[j]) %= MOD; } (tmp *= q_pow(k, MOD-2)) %= MOD; vc.pb(tmp); } printf("%lld ", linear_seq::gao(vc, n)); } } return 0; }
C
D
思路:
既然要选择第K小的,我们可以从小到大做。每次通过最小的一个最小团扩展,可以利用bitset优化判断扩展的可行性。利用优先队列,从其中取出的第k个就是答案。
队友代码:
#include<bits/stdc++.h> using namespace std; #define pb push_back #define fi first #define se second #define debug(x) cerr<<#x << " := " << x << endl; #define bug cerr<<"-----------------------"<<endl; #define FOR(a, b, c) for(int a = b; a <= c; ++ a) typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; template<class T> void _R(T &x) { cin >> x; } void _R(int &x) { scanf("%d", &x); } void _R(ll &x) { scanf("%lld", &x); } void _R(double &x) { scanf("%lf", &x); } void _R(char &x) { scanf(" %c", &x); } void _R(char *x) { scanf("%s", x); } void R() {} template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); } template<typename T> inline T read(T&x){ x=0;int f=0;char ch=getchar(); while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x=f?-x:x; } const int inf = 0x3f3f3f3f; const int mod = 1e9+7; /**********showtime************/ const int maxn = 109; char str[maxn]; struct node{ ll val; bitset<109>bs; bool operator<(const node & o) const{ return val > o.val; } }a[maxn]; int main(){ int n,k; scanf("%d%d", &n, &k); for(int i=1; i<=n; i++) { scanf("%lld", &a[i].val); } for(int i=1; i<=n; i++) { scanf("%s", str+1); for(int j=1; j<=n; j++) { if(str[j] == '1')a[i].bs.set(j); } } priority_queue<node>que; node s; s.val = 0; s.bs.reset(); que.push(s); int flag = 0;ll res; while(!que.empty()) { node u = que.top(); que.pop(); k -- ; if(k == 0) { flag = 1; res = u.val; break; } int mx = 1; for(int i=1; i<=n; i++) { if(u.bs[i] == 1) mx = i + 1; } for(int i=mx; i<=n; i++) { if((u.bs & a[i].bs) == u.bs) { u.bs.set(i); u.val += a[i].val; que.push(u); u.bs.reset(i); u.val -= a[i].val; } } } if(flag) printf("%lld ", res); else puts("-1"); return 0; }
E
思路:
考虑从第$i$行到第$i+1$行的转移,假设第$i$行为"10010"
设 $dp_{i,j}$表示到第$i$行第$j$列的方案数。
于是相邻两项dp的转移过程可以看成一个矩阵乘以一个向量(如果暂时不考虑当前行的横向转移)。 多项之间的转移可以看成矩阵连乘再乘以一个向量。
于是用线段树维护矩阵的乘法,线段树每个叶子节点表示一个矩阵。 单次修改复杂度O($log(n)m^3$),其中$m^3$是矩阵乘法的复杂度。
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define y1 y11 #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb emplace_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pli pair<LL, int> #define pii pair<int, int> #define piii pair<pii, int> #define pdd pair<double, double> #define mem(a, b) memset(a, b, sizeof(a)) #define debug(x) cerr << #x << " = " << x << " "; #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); //head const int N = 5e4 + 5; const int MOD = 1e9 + 7; int n, q, m, op, x, y; string b[N]; struct Matrix { int a[10][10]; inline void init() {memset(a, 0, sizeof a);} inline void _init() { init(); for (int i = 0; i < m; ++i) a[i][i] = 1; } inline void reset(int p) { init(); for (int i = 0; i < m; ++i) { for (int j = i; j >= 0; --j) if(b[p][j] == '0') a[j][i] = 1; else break; for (int j = i; j < m; ++j) if(b[p][j] == '0') a[j][i] = 1; else break; } } inline Matrix operator * (const Matrix & rhs) const { Matrix res; res.init(); for (int i = 0; i < m; ++i) { for (int j = 0; j < m; ++j) { if(a[i][j]) { for (int k = 0; k < m; ++k) (res.a[i][k] += a[i][j]*1LL*rhs.a[j][k]%MOD) %= MOD; } } } return res; } }tree[N<<2]; inline void push_up(int rt) { tree[rt] = tree[rt<<1]*tree[rt<<1|1]; } void build(int rt, int l, int r) { if(l == r) { tree[rt].reset(l); return ; } int m = l+r >> 1; build(ls); build(rs); push_up(rt); } void update(int p, int rt, int l, int r) { if(l == r) { tree[rt].reset(l); return ; } int m = l+r >> 1; if(p <= m) update(p, ls); else update(p, rs); push_up(rt); } int main(){ fio; cin >> n >> m >> q; for (int i = 1; i <= n; ++i) cin >> b[i]; build(1, 1, n); while(q--) { cin >> op >> x >> y; if(op == 1) { if(b[x][y-1] == '1') b[x][y-1] = '0'; else b[x][y-1] = '1'; update(x, 1, 1, n); } else { cout << tree[1].a[x-1][y-1] << " "; } } return 0; }
F
思路:折半枚举,对于每一半的每个状态记录每一行状态为1的行和,最后暴力更新答案。
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define LL long long #define pb push_back const int manx=1e6+10; int n; int a[30][30]; LL mp[(1<<15)][30]; LL mq[(1<<15)][30]; vector<int> vc[18]; int main(){ scanf("%d",&n); for(int i=0;i<2*n;i++){ for(int j=0;j<2*n;j++){ scanf("%d",&a[i][j]); } } int up = 1<<n; for(int i=0;i<up;i++){ for(int j=0;j<n;j++){ if(i&(1<<j)){ for (int k = 0; k < 2*n; ++k) { mp[i][k] += a[k][j]; } } } } for(int i=0;i<up;i++){ for(int j=0;j<n;j++){ if(i&(1<<j)){ for (int k = 0; k < 2*n; ++k) { mq[i][k] += a[k][j+n]; } } } vc[n-__builtin_popcount(i)].pb(i); } LL ans = 0; for (int i = 0; i < up; ++i) { int x = __builtin_popcount(i); for (int j : vc[x]){ LL t = 0; for (int k = 0; k < n; ++k) { if((i&(1<<k)) == 0) t += mp[i][k]+mq[j][k]; if((j&(1<<k)) == 0) t += mp[i][n+k]+mq[j][n+k]; } ans = max(ans, t); } } printf("%lld ", ans); return 0; }
G
思路:平面直线图模板题。
H
思路:将每个最大面积和次大面积的左上角扔进map里去重。
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define y1 y11 #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb emplace_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pli pair<LL, int> #define pii pair<int, int> #define piii pair<pii, int> #define pdd pair<double, double> #define mem(a, b) memset(a, b, sizeof(a)) #define debug(x) cerr << #x << " = " << x << " "; #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); //head const int N = 1e3 + 5; int l[N][N], r[N][N], up[N][N], a[N][N], n, m; char s[N][N]; map<int, vector<pii>, greater<int>> mp; int main() { scanf("%d %d",&n, &m); for (int i = 1; i <= n; ++i) scanf("%s", s[i]+1); for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) a[i][j] = s[i][j]-'0'; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if(a[i][j]) l[i][j] = l[i][j-1]+1; } for (int j = m; j >= 1; --j) { if(a[i][j]) r[i][j] = r[i][j+1]+1; } } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if(a[i][j]) { up[i][j] = up[i-1][j]+1; if(a[i-1][j]) { l[i][j] = min(l[i-1][j], l[i][j]); r[i][j] = min(r[i-1][j], r[i][j]); } int A = up[i][j], B = r[i][j]+l[i][j]-1; mp[A*B].pb(i-up[i][j]+1, j-l[i][j]+1); mp[A*(B-1)].pb(i-up[i][j]+1, j-l[i][j]+1); mp[(A-1)*B].pb(i-up[i][j]+1, j-l[i][j]+1); } } } int t = 0; for (auto &it : mp) { sort(it.se.begin(), it.se.end()); it.se.erase(unique(it.se.begin(), it.se.end()), it.se.end()); for (int i = 0; i < it.se.size(); ++i) { ++t; if(t == 2) { printf("%d ", it.fi); return 0; } } } printf("0 "); return 0; }
I
J
思路:将每个答案的区间包含的点扣出来然后求前缀和,详见队友博客
队友代码:
#include <bits/stdc++.h> using namespace std; #define pb push_back #define fi first #define se second #define debug(x) cerr<<#x << " := " << x << endl; #define bug cerr<<"-----------------------"<<endl; #define FOR(a, b, c) for(int a = b; a <= c; ++ a) typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; template<class T> void _R(T &x) { cin >> x; } void _R(int &x) { scanf("%d", &x); } void _R(ll &x) { scanf("%lld", &x); } void _R(double &x) { scanf("%lf", &x); } void _R(char &x) { scanf(" %c", &x); } void _R(char *x) { scanf("%s", x); } void R() {} template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); } template<typename T> inline T read(T&x){ x=0;int f=0;char ch=getchar(); while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x=f?-x:x; } const int inf = 0x3f3f3f3f; const ll inff = 0x3f3f3f3f3f3f3f3f; const int mod = 1e9+7; /**********showtime************/ const int maxm = 2e7+9; const int maxn = 1e6+9; int le[maxn],ri[maxn]; int lto[maxn],rto[maxn]; ll f[maxm]; int g(int x) { return x + 10000000; } int main(){ int n; scanf("%d", &n); for(int i=1; i<=n; i++) scanf("%d%d", &le[i], &ri[i]); int sum = 0; /// 向右扩展 le[n+1] = 1000000000; for(int i=1; i<=n; i++) { sum += ri[i] - le[i] + 1; rto[i] = min(sum, le[i+1] - ri[i] - 1); sum -= le[i+1] - ri[i] - 1; if(sum < 0) sum = 0; } /// 向左扩展 sum = 0; ri[0] = -1; for(int i=n; i>=1; i--) { sum += ri[i] - le[i] + 1; lto[i] = min(sum , le[i] - ri[i-1] -1); sum -= le[i] - ri[i-1] - 1; if(sum < 0) sum = 0; } ///计算每个点的前缀和。lowsum保存前缀和比当前点小的个数 ll ans = 0, lowsum = 0; int s = 0, pos = 0; f[g(0)] = 1; for(int i=1; i<=n; i++) { for(int j=max(pos, le[i] - lto[i]); j<=ri[i] + rto[i]; j++) { if(j>=le[i] && j <= ri[i]) { lowsum += f[g(s)]; s++; f[g(s)]++; ans += lowsum; } else { s--; lowsum -= f[g(s)]; f[g(s)]++; ans += lowsum; } // cout<<j<<" "<<lowsum<<endl; pos = j+1; } } // cout<<endl; printf("%lld ", ans); return 0; }
题号 | 标题 | 团队的状态 |
---|---|---|
A | Graph Games | 通过 |
B | Crazy Binary String | 通过 |
C | Guessing ETT | 未通过 |
D | Big Integer | 通过 |
E | Trees in the Pocket II | 未通过 |
F | Planting Trees | 通过 |
G | Removing Stones | 通过 |
H | Magic Line | 通过 |
I | Median | 通过 |
J | LRU management | 通过 |
A
思路:将点按度数分成两种点,大于$sqrt{m}$的称为大点,否则称为小点。然后再对边分块,修改边的话,边缘块直接修改,整块直接反转。
然后还需要先预处理出每个块对大点的贡献。对于每个小点暴力查询连接的每条边是否反转;对于每个大点,考虑每个块是否反转,并对它产生多少贡献。
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define y1 y11 #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb push_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pli pair<LL, int> #define pii pair<int, int> #define piii pair<pii, int> #define pdd pair<double, double> #define mem(a, b) memset(a, b, sizeof(a)) #define debug(x) cerr << #x << " = " << x << " "; #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); //head struct FastIO { static const int S = 4e6; int wpos; char wbuf[S]; FastIO() : wpos(0) {} inline int xchar() { static char buf[S]; static int len = 0, pos = 0; if (pos == len) pos = 0, len = fread(buf, 1, S, stdin); if (pos == len) exit(0); return buf[pos++]; } inline int xuint() { int c = xchar(), x = 0; while (c <= 32) c = xchar(); for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0'; return x; } inline int xint() { int s = 1, c = xchar(), x = 0; while (c <= 32) c = xchar(); if (c == '-') s = -1, c = xchar(); for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0'; return x * s; } inline void xstring(char *s) { int c = xchar(); while (c <= 32) c = xchar(); for (; c > 32; c = xchar()) * s++ = c; *s = 0; } inline void wchar(int x) { if (wpos == S) fwrite(wbuf, 1, S, stdout), wpos = 0; wbuf[wpos++] = x; } inline void wint(int x) { if (x < 0) wchar('-'), x = -x; char s[24]; int n = 0; while (x || !n) s[n++] = '0' + x % 10, x /= 10; while (n--) wchar(s[n]); wchar(' '); } inline void wstring(const char *s) { while (*s) wchar(*s++); } ~FastIO() { if (wpos) fwrite(wbuf, 1, wpos, stdout), wpos = 0; } } io; const int N = 1e5 + 5; vector<int> g[N]; int T, n, m, d[N], u[N*2], v[N*2], op, l, r, q, id[N*2]; LL val[N], res[N], f[N][500]; bool ty[N]; struct BLOCK { int bl[N*2], block, blo[1000]; inline void init() { for (int i = 1; i <= m; ++i) bl[i] = (i-1)/block + 1; for (int i = 1; i <= bl[m]; ++i) blo[i] = 0; } inline void update(int L, int R) { if(bl[L] == bl[R]) { for (int i = L; i <= R; ++i) res[u[i]] ^= val[v[i]], res[v[i]] ^= val[u[i]]; return ; } for (int i = L; i <= bl[L]*block; ++i) res[u[i]] ^= val[v[i]], res[v[i]] ^= val[u[i]]; for (int i = bl[L]+1; i <= bl[R]-1; ++i) blo[i] ^= 1; for (int i = (bl[R]-1)*block+1; i <= R; ++i) res[u[i]] ^= val[v[i]], res[v[i]] ^= val[u[i]]; } }b; int main() { mt19937 mt_rand(time(NULL)); T = io.xint(); while(T--) { n = io.xint(); m = io.xint(); for (int i = 1; i <= n; ++i) val[i] = mt_rand()%LONG_MAX; for (int i = 1; i <= m; ++i) u[i] = io.xint(), v[i] = io.xint(), g[u[i]].pb(i), g[v[i]].pb(i), d[u[i]]++, d[v[i]]++; int blo = sqrt(m)+1; b.block = blo; b.init(); for (int i = 1; i <= n; ++i) { if(d[i] <= blo) ty[i] = 0; else ty[i] = 1; } for (int i = 1; i <= n; ++i) if(ty[i]) for (int j = 1; j <= b.bl[m]; ++j) f[i][j] = 0; for (int i = 1; i <= n; ++i) { for (int id : g[i]) { int y = u[id]^v[id]^i; res[i] ^= val[y]; if(ty[i]) f[i][b.bl[id]] ^= val[y]; } } q = io.xint(); for (int i = 1; i <= q; ++i) { op = io.xint(); l = io.xint(); r = io.xint(); if(op == 1) { b.update(l, r); } else { LL v1 = res[l], v2 = res[r]; if(ty[l]) {for (int j = 1; j <= b.bl[m]; ++j) if(b.blo[j]) v1 ^= f[l][j];} else for (int id : g[l]) if(b.blo[b.bl[id]]) v1 ^= val[u[id]^v[id]^l]; if(ty[r]) {for (int j = 1; j <= b.bl[m]; ++j) if(b.blo[j]) v2 ^= f[r][j];} else for (int id : g[r]) if(b.blo[b.bl[id]]) v2 ^= val[u[id]^v[id]^r]; putchar((v1==v2)+'0'); } } putchar(' '); for(int i = 1; i <= n; ++i) d[i] = 0, g[i].clear(), res[i] = 0; for (int i = 1; i <= m; ++i) id[i] = 0; } return 0; }
B
思路:对于最长子段的计算,只要把0看成-1,对于每个前缀和记录最前面出现的位置
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb push_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pii pair<int, int> #define piii pair<pii, int> #define mem(a, b) memset(a, b, sizeof(a)) #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout); //head const int N = 1e5 + 10; char s[N]; int n, sum[N], a, b, c1, c0; map<int, int> mp; int main() { scanf("%d", &n); scanf("%s", s+1); for (int i = 1; i <= n; ++i) if(s[i] == '1') c1++; else c0++; b = min(c1, c0)*2; mp[0] = 0; for (int i = 1; i <= n; ++i) { if(s[i] == '1') sum[i] = sum[i-1]+1; else sum[i] = sum[i-1]-1; if(mp.find(sum[i]) != mp.end()) a = max(a, i-mp[sum[i]]); else mp[sum[i]] = i; } printf("%d %d ", a, b); return 0; }
C
D
思路:首先有一个公式$frac{x}{d}\%k = frac{x\%k*d}{d}$。那么原式$frac{10^x-1}{9}\%p$可以化简$10^x = 1(\%(9*p))$。或者模数不乘$9$,但$p=3$时要特判。
当$p = 2, 5$时,答案肯定是$0$。否则,求出最小的x满足等式,这个可以用费马小定理或者BSGS。然后就是求多少对$(i, j)$使得$x | i^j$。我们先把$x$分解
质因数$x={p_1}^{a_1} {p_2}^{a_2}...{p_n}^{a_n}$,然后枚举$j$,那么对于一个固定的$j$,我们发现$y = p_{1}^{lceilfrac{a_{1}}{j} ceil}p_{2}^{lceilfrac{a_{2}}{j} ceil}...p_{n}^{lceilfrac{a_{n}}{j} ceil} $的倍数的$j$次方一定是$x$的倍数, 那么就是求小于$n$的数中有多少个是$y$的倍数。当$j ge 30$时,$y$的质因子的幂次都变成了$1$。
代码:
#include<bits/stdc++.h> #define ll long long #define LL long long using namespace std; LL qpow(LL n, LL k) { LL ans = 1; if(k == -1) return 0; while(k) { if(k&1) ans = (ans*n); n = (n*n); k >>= 1; } return ans; } unordered_map<int, int> mp; LL q_pow(LL n, LL k, LL p) { LL ans = 1; if(k == -1) return 0; while(k) { if(k&1) ans = (ans*n) % p; n = (n*n) % p; k >>= 1; } return ans; } int BSGS(int a, int b, int p){ int m = sqrt(p)+1, s = b; mp.clear(); for(int i = 0; i < m; ++i){ mp[s]=i; s= (s*1LL*a)%p; } int t = q_pow(a, m, p); s = 1; for(int i = 1; i <= m; ++i){ s = (s*1LL*t)%p; if(mp.find(s) != mp.end()) return i*m-mp[s]; } return -1; } int p,n,m; vector<pair<int,int> > vs; void make(int p){ vs.clear(); for(int i=2;i*i<=p;i++){ if(p%i==0){ int c=0; while(p%i==0){ c++; p/=i; } vs.push_back({i,c}); } } if(p!=1) vs.push_back({p,1}); ll num=0; ll temp=1; for(int j=1;j<=min(30,m);j++){ temp=1; for(int i=0; i<vs.size(); i++){ temp=temp*qpow(vs[i].first,ceil(1.0*vs[i].second/j)); } num+=n/temp; } if (m>30) num+=1ll*(m-30)*(n/temp); printf("%lld ",num); } int main(){ int T; scanf("%d",&T); while(T--){ scanf("%d %d %d",&p,&n,&m); if(p==2 || p==5) { printf("0 "); continue; } int x=BSGS(10,1,p);// cout<<x<<endl; if(p==3) x=3; make(x); } }
E
F
思路:用枚举上边界l和下边界r,先对于每一列求出最大值最小值,然后用单调队列维护。这道题很卡常,有个用两次单调队列的$n^3$写法被卡掉了。
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb push_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pii pair<int, int> #define piii pair<pii, int> #define mem(a, b) memset(a, b, sizeof(a)) #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout); //head const int N = 505; const int INF = 0x3f3f3f3f; int a[N][N], mn[N], mx[N]; int q1[N*2], q2[N*2], T, n, m; int main() { scanf("%d", &T); while(T--){ scanf("%d %d", &n, &m); for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) scanf("%d", &a[i][j]); int ans = 0; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) mn[j] = INF, mx[j] = -INF; for (int j = i; j <= n; ++j) { for (int k = 1; k <= n; ++k) mn[k] = min(a[j][k], mn[k]), mx[k] = max(a[j][k], mx[k]); int le1 = N, ri1 = N-1; int le2 = N, ri2 = N-1; int pre = 0; for (int k = 1; k <= n; ++k) { while(le1 <= ri1 && mn[q1[ri1]] >= mn[k]) ri1--; q1[++ri1] = k; while(le2 <= ri2 && mx[q2[ri2]] <= mx[k]) ri2--; q2[++ri2] = k; while(pre < k && mx[q2[le2]]-mn[q1[le1]] > m) { ++pre; while(le1 <= ri1 && q1[le1] <= pre) le1++; while(le2 <= ri2 && q2[le2] <= pre) le2++; } if(pre < k && mx[q2[le2]] - mn[q1[le1]] <=m) ans = max(ans, (k - pre)*(j-i+1)); } } } printf("%d ", ans); } return 0; }
G
思路:分治,对于每个分治的区间$[L,R]$,求出最大值的位置$p$,然后枚举$[L,p]$或者$[p,R]$中小的区间中的每个位置,然后找另一个端点的位置。
然后递归区间$[L,p-1]$和区间$[p+1,R]$。时间复杂度$O(n*log(n))$
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define y1 y11 #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb emplace_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pli pair<LL, int> #define pii pair<int, int> #define piii pair<pii, int> #define pdd pair<double, double> #define mem(a, b) memset(a, b, sizeof(a)) #define debug(x) cerr << #x << " = " << x << " "; #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); //head const int N = 3e5 + 5; int T, n, a[N], st[N][20], lg[N]; LL sum[N]; LL ans = 0; inline void init() { for (int i = n; i >= 1; --i) { st[i][0] = i; for (int j = 1; i+(1<<j-1)-1 <= n; ++j) { if(a[st[i][j-1]] > a[st[i+(1<<j-1)][j-1]]) st[i][j] = st[i][j-1]; else st[i][j] = st[i+(1<<j-1)][j-1]; } } } inline int get_max(int L, int R) { int k = lg[R-L+1], x = st[L][k], y = st[R-(1<<k)+1][k]; if(a[x] > a[y]) return x; else return y; } void solve(int L, int R) { if(L >= R) return ; int p = get_max(L, R); if(p-L < R-p) { int j = p; for (int i = L; i <= p; ++i) { while(j <= R && sum[j]-sum[i-1] < 2*a[p]) ++j; ans += R-j+1; } } else { int j = p; for (int i = R; i >= p; --i) { while(j >= L && sum[i]-sum[j==0?j:j-1] < 2*a[p]) --j; ans += j-L+1; } } solve(L, p-1); solve(p+1, R); } int main() { for (int i = 2; i < N; ++i) lg[i]=lg[i>>1]+1; scanf("%d", &T); while(T--) { scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), sum[i] = sum[i-1]+a[i]; init(); ans = 0; solve(1, n); printf("%lld ", ans); } return 0; }
H
思路:构造
代码:
#include<bits/stdc++.h> using namespace std; #define ll long long const int maxn=2e3+10; vector<int> vs[maxn]; int32_t main(){ int T; scanf("%d",&T); while(T--){ int n; scanf("%d",&n); for(int i=1;i<=n;i++){ int x,y; scanf("%d %d",&x,&y); x+=1000; y+=1000; vs[x].push_back(y); } int temp=0; for(int i=0;i<=2000;i++){ if(temp+vs[i].size()>=n/2){ int d=n/2-temp; sort(vs[i].begin(),vs[i].end()); int y=vs[i][d-1]; if(y>=1000){ int x1=i+1; x1-=1000; int y1=-1; y1-=1000; int x2=i+3; x2-=1000; int y2=-2*y-4; y2-=1000; printf("%d %d %d %d ",x1,y1,x2,y2); } else { int x1=i-1; int y1=2001; int x2=i-3; int y2=-2*y+6003-1; printf("%d %d %d %d ",x1-1000,y1-1000,x2-1000,y2-1000); } break; } temp+=vs[i].size(); } for(int i=0;i<=2000;i++) vs[i].clear(); } }
I
思路:如果可以构造,那么$a_i$一定可以选择$b_i,b_{i-1},b_{i-2}$中的一个值,具体证明看题解。那么可以想到一个状态$dp[i][j][k]$,其中,$j$和$k$
分别表示$i$和$i-1$这两个位置选择的$b_i$和本身之间的距离,那判断一下相邻两个之间的转移可不可行就可以转移了。
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define y1 y11 #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb push_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pli pair<LL, int> #define pii pair<int, int> #define piii pair<pii, int> #define pdd pair<double, double> #define mem(a, b) memset(a, b, sizeof(a)) #define debug(x) cerr << #x << " = " << x << " "; #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); //head const int N = 1e5 + 5; bool dp[N][3][3]; int pre[N][3][3]; int T, n, b[N], a[N]; inline int ck(int x, int y, int z) { if(b[x] >= b[y] && b[x] >= b[z]) return max(b[y], b[z]); if(b[y] >= b[x] && b[y] >= b[z]) return max(b[x], b[z]); return max(b[x], b[y]); } int main() { scanf("%d", &T); while(T--) { scanf("%d", &n); for (int i = 1; i <= n-2; ++i) scanf("%d", &b[i]); if(n == 3) { for (int i = 1; i <= 3; ++i) printf("%d ", b[1]); printf(" "); continue; } for (int i = 1; i <= n; ++i) for (int j = 0; j < 3; ++j) for (int k = 0; k < 3; ++k) dp[i][j][k] = 0; for (int i = 1; i <= n; ++i) { if(i == 1) ; else if(i == 2) { for (int j = 0; j < 3; ++j) { if(2-j < 1) break; for (int k = 0; k < 3; ++k) { if(1-k < 1) break; dp[i][j][k] = 1; } } } else { for (int j = 0; j < 3; ++j) { for (int k = 0; k < 3; ++k) { if(dp[i-1][j][k]) { for (int l = 0; l < 3; ++l) { if(i-l <= n-2) { if(ck(i-2-k, i-1-j, i-l) == b[i-2]) dp[i][l][j] = 1, pre[i][l][j] = k; } } } } } } } int x, y, z; bool f = false; for (int j = 0; j < 3; ++j) for (int k = 0; k < 3; ++k) if(dp[n][j][k]) { f = true; x = n; y = j; z = k; break; } if(f) { while(x) { a[x] = b[x-y]; int tmp = z; z = pre[x][y][z]; y = tmp; x--; } for (int i = 1; i <= n; ++i) printf("%d%c", a[i], " "[i==n]); } else printf("-1 "); } return 0; }
J
思路:用平衡树维护,其实用set就可以了,记录一下每个串最后的位置,如果这个串被删除,也要记得删除位置
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb push_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pii pair<int, int> #define piii pair<pii, int> #define mem(a, b) memset(a, b, sizeof(a)) #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout); //head const int N = 5e5 + 10; int ch[N][2], val[N], cnt[N], V[N], fa[N], sz[N], ncnt = 0, rt = 0; string tmp[N]; inline int ck(int x) { return ch[fa[x]][1] == x; } inline void push_up(int x) { sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x]; } void Rotate(int x) { int y = fa[x], z = fa[y]; int k = ck(x), w = ch[x][k^1]; ch[y][k] = w, fa[w] = y; ch[z][ck(y)] = x, fa[x] = z; ch[x][k^1] = y, fa[y] = x; push_up(y), push_up(x); } void Splay(int x, int goal = 0) { while(fa[x] != goal) { int y = fa[x], z = fa[y]; if(z != goal) { if(ck(x) == ck(y)) Rotate(y); else Rotate(x); } Rotate(x); } if(!goal) rt = x; } void Find(int x) { if(!rt) return ; int cur = rt; while(ch[cur][x>val[cur]] && x != val[cur]) cur = ch[cur][x>val[cur]]; Splay(cur); } void Insert(int x, int y, string s) { int cur = rt, p = 0; while(cur && val[cur] != x) { p = cur; cur = ch[cur][x>val[cur]]; } if(cur) cnt[cur]++; else { cur = ++ncnt; if(p) ch[p][x>val[p]] = cur; fa[cur] = p; ch[cur][0] = ch[cur][1] = 0; val[cur] = x; V[cur] = y; tmp[cur] = s; cnt[cur] = sz[cur] = 1; } Splay(cur); } int Kth(int k) { int cur = rt; while(true) { if(ch[cur][0] && k <= sz[ch[cur][0]]) cur = ch[cur][0]; else if(k > sz[ch[cur][0]] + cnt[cur]) k -=sz[ch[cur][0]] + cnt[cur], cur = ch[cur][1]; else return cur; } } inline int get_min(int x) { while(x && ch[x][0]) x = ch[x][0]; return x; } inline int get_max(int x) { while(x && ch[x][1]) x = ch[x][1]; return x; } int Pre(int x) { Find(x); if(val[rt] < x) return rt; if(!ch[rt][0]) return -1; int cur = ch[rt][0]; while(ch[cur][1]) cur = ch[cur][1]; return cur; } int Succ(int x) { Find(x); if(val[rt] > x) return rt; if(!ch[rt][1]) return -1; int cur = ch[rt][1]; while(ch[cur][0]) cur = ch[cur][0]; return cur; } void Remove(int x) { int last = Pre(x), next = Succ(x); Splay(last), Splay(next, last); int del = ch[next][0]; if(cnt[del] > 1) cnt[del]--, Splay(del); else ch[next][0] = 0, push_up(next), push_up(last); } void delete_root() { if(ch[rt][1]) { int cur = ch[rt][1]; while(cur && ch[cur][0]) cur = ch[cur][0]; Splay(cur, rt); ch[cur][0] = ch[rt][0]; fa[ch[cur][0]] = cur; rt = cur; } else rt = ch[rt][0]; fa[rt] = 0; if(rt) push_up(rt); } inline void init() { ncnt = rt = ch[0][0] = ch[0][1] = fa[0] = sz[0] = cnt[0] = val[0] = 0; // V[0] = -10; } int q, m, op, v, T; string s; unordered_map<string, int> mp; int main() { fio; cin >> T; while(T--) { init(); mp.clear(); Insert(-1, -10, "0"); Insert(N-1, -10, "0"); cin >> q >> m; int now = 0; for (int i = 1; i <= q; ++i){ cin >> op >> s >> v; int res = 0; if(op == 0) { if(mp.find(s) == mp.end()) { mp[s] = ++now; Insert(now, v, s); res = v; } else { Find(mp[s]); res = V[rt]; Remove(mp[s]); mp[s] = ++now; Insert(now, res, s); } cout << res << " "; } else { if(mp.find(s) == mp.end()) { cout << "Invalid "; } else { if(v == 0) { Find(mp[s]); cout << V[rt] << " "; } else if(v == -1) { int cur = Pre(mp[s]); if(V[cur] == -10) cout << "Invalid "; else cout << V[cur] << " "; } else { int cur = Succ(mp[s]); if(V[cur] == -10) cout << "Invalid "; else cout << V[cur] << " "; } } } if(sz[rt]-2 > m) { int cur = Kth(2); Splay(cur); delete_root(); mp.erase(tmp[cur]); } } } return 0; }
题号 | 标题 | 团队的状态 |
---|---|---|
A | meeting | 通过 |
B | xor | 通过 |
C | sequence | 通过 |
D | triples I | 通过 |
E | triples II | 通过 |
F | merge | 通过 |
G | tree | 未通过 |
H | RNGs | 未通过 |
I | string | 通过 |
J | free | 通过 |
K | number | 通过 |
A
思路:虚树直径的一半。
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define y1 y11 #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb emplace_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pli pair<LL, int> #define pii pair<int, int> #define piii pair<pii, int> #define pdd pair<double, double> #define mem(a, b) memset(a, b, sizeof(a)) #define debug(x) cerr << #x << " = " << x << " "; #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); //head const int N = 1e5 + 5; vector<int> g[N]; int a[N], sz[N], sum[N], n, k, u, v, s, mx; void dfs(int u, int o, int d) { if(a[u]) { if(d > mx) { mx = d; s = u; } } for (int v : g[u]) { if(v != o){ dfs(v, u, d+1); } } } int main() { scanf("%d %d", &n, &k); for (int i = 1; i < n; ++i) { scanf("%d %d", &u, &v); g[u].pb(v); g[v].pb(u); } for (int i = 1; i <= k; ++i) scanf("%d", &u), ++a[u]; dfs(u, u, 0); dfs(s, s, 0); if(mx%2) printf("%d ", (mx+1)/2); else printf("%d ", mx/2); return 0; }
B
思路:线性基求交+线段树。建树的复杂度是$O(n*32*32)$,查询时不需要把需要查询区间的交算出来,不然单次查询复杂度$O(32*32*log(n))$,
只需要判断这段区间在线段树上的每个节点是不是可以表示$x$就可以了,这样单次查询复杂度$O(32*log(n))$。
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define y1 y11 #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb emplace_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pli pair<LL, int> #define pii pair<int, int> #define piii pair<pii, int> #define pdd pair<double, double> #define mem(a, b) memset(a, b, sizeof(a)) #define debug(x) cerr << #x << " = " << x << " "; #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); //head const int N = 5e4 + 5; struct LinearBase { LL v[32]; inline void clr() {memset(v, 0, sizeof(v));} inline void ins(LL a) { for (int i = 31; i >= 0; --i) { if(a&(1LL<<i)) { if(!v[i]) { v[i] = a; break; } a ^= v[i]; } } } inline bool can_ex(LL a) { for (int i = 31; i >= 0; --i) if((a^v[i]) < a) a ^= v[i]; return a == 0; } //交 inline friend LinearBase operator * (const LinearBase &a, const LinearBase &b) { LinearBase all, c, d; all.clr(), c.clr(), d.clr(); for (int i = 31; i >= 0; --i) { all.v[i] = a.v[i]; d.v[i] = 1LL<<i; } for (int i = 31; i >= 0; --i) { if(b.v[i]) { LL v = b.v[i], k = 0; bool can = true; for (int j = 31; j >= 0; --j) { if(v&(1LL<<j)) { if(all.v[j]) { v ^= all.v[j]; k ^= d.v[j]; } else { can = false; all.v[j] = v; d.v[j] = k; break; } } } if(can) { LL v = 0; for (int j = 31; j >= 0; --j) { if(k&(1LL<<j)) { v ^= a.v[j]; } } c.ins(v); } } } return c; } }tree[N<<2]; vector<LL> vc[N]; inline void push_up(int rt) { tree[rt] = tree[rt<<1]*tree[rt<<1|1]; } void build(int rt, int l, int r) { if(l == r) { tree[rt].clr(); for (LL x : vc[l]) tree[rt].ins(x); return ; } int m = l+r >> 1; build(ls); build(rs); push_up(rt); } bool query(int L, int R, LL a, int rt, int l, int r) { if(L <= l && r <= R) return tree[rt].can_ex(a); int m = l+r >> 1; if(L <= m && m < R) return query(L, R, a, ls)&query(L, R, a, rs); if(L <= m) return query(L, R, a, ls); else return query(L, R, a, rs); } int n, m, t, l, r; LL a; int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; ++i) { scanf("%d", &t); vc[i].resize(t); for (int j = 0; j < t; ++j) scanf("%lld", &vc[i][j]); } build(1, 1, n); while(m--) { scanf("%d %d %lld", &l, &r, &a); if(query(l, r, a, 1, 1, n)) printf("YES "); else printf("NO "); } return 0; }
C
思路:南昌邀请赛原题。
先对b数组求个前缀和,然后用单调栈求出以每个位置$p$为最小值左端点的最左边$L$和右端点的最右边$R$。
如果$a[p] > 0$,用$maxleft(sum[i], iin[p, R] ight)- minleft(sum[i], iin[L-1, p-1] ight)$;
如果$a[p] < 0$,用$minleft(sum[i], iin[p, R] ight)- maxleft(sum[i], iin[L-1, p-1] ight)$。
方法一(单调栈+线段树$O(nlog(n))2500ms$)
代码:
#include <bits/stdc++.h> using namespace std; #define LL long long #define fi first #define se second #define pb push_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r const int N = 3e6 + 5; int a[N], b[N], pre[N], suf[N]; LL sum[N], mx[N<<2], mn[N<<2]; stack<int> st; int n; void push_up(int rt) { mn[rt] = min(mn[rt<<1], mn[rt<<1|1]); mx[rt] = max(mx[rt<<1], mx[rt<<1|1]); } void build(int rt, int l, int r) { if(l == r) { mx[rt] = mn[rt] = sum[l]; return ; } int m = l+r >> 1; build(ls); build(rs); push_up(rt); } LL querymx(int L, int R, int rt, int l, int r) { if(L <= l && r <= R) return mx[rt]; int m = l+r >> 1; LL ans = LONG_MIN; if(L <= m) ans = max(ans, querymx(L, R, ls)); if(R > m) ans = max(ans, querymx(L, R, rs)); return ans; } LL querymn(int L, int R, int rt, int l, int r) { if(L <= l && r <= R) return mn[rt]; int m = l+r >> 1; LL ans = LONG_MAX; if(L <= m) ans = min(ans, querymn(L, R, ls)); if(R > m) ans = min(ans, querymn(L, R, rs)); return ans; } int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); for (int i = 1; i <= n; ++i) scanf("%d", &b[i]); for (int i = 1; i <= n; ++i) sum[i] = sum[i-1] + b[i]; build(1, 0, n); a[0] = a[n+1] = INT_MIN; st.push(0); for (int i = 1; i <= n; ++i) { while(!st.empty() && a[st.top()] >= a[i]) st.pop(); pre[i] = st.top(); st.push(i); } while(!st.empty()) st.pop(); st.push(n+1); for (int i = n; i >= 1; --i) { while(!st.empty() && a[st.top()] >= a[i]) st.pop(); suf[i] = st.top(); st.push(i); } LL ans = -(1LL<<61); for (int i = 1; i <= n; ++i) { int l = pre[i], r = i-1; int ll = i, rr = suf[i]-1; if(a[i] < 0) { ans = max(ans, a[i]*(querymn(ll, rr, 1, 0, n)-querymx(l, r, 1, 0, n))); } else if(a[i] > 0) { ans = max(ans, a[i]*(querymx(ll, rr, 1, 0, n)-querymn(l, r, 1, 0, n))); } } printf("%lld ", ans); return 0; }
方法二(笛卡尔树+快读$O(n)350ms$,这个快读优化了1200ms,出题人为了卡$log$连读入都卡掉了)
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define y1 y11 #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb emplace_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pli pair<LL, int> #define pii pair<int, int> #define piii pair<pii, int> #define pdd pair<double, double> #define mem(a, b) memset(a, b, sizeof(a)) #define debug(x) cerr << #x << " = " << x << " "; #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); //head struct FastIO { static const int S = 4e6; int wpos; char wbuf[S]; FastIO() : wpos(0) {} inline int xchar() { static char buf[S]; static int len = 0, pos = 0; if (pos == len) pos = 0, len = fread(buf, 1, S, stdin); if (pos == len) exit(0); return buf[pos++]; } inline int xuint() { int c = xchar(), x = 0; while (c <= 32) c = xchar(); for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0'; return x; } inline int xint() { int s = 1, c = xchar(), x = 0; while (c <= 32) c = xchar(); if (c == '-') s = -1, c = xchar(); for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0'; return x * s; } inline void xstring(char *s) { int c = xchar(); while (c <= 32) c = xchar(); for (; c > 32; c = xchar()) * s++ = c; *s = 0; } inline void wchar(int x) { if (wpos == S) fwrite(wbuf, 1, S, stdout), wpos = 0; wbuf[wpos++] = x; } inline void wint(int x) { if (x < 0) wchar('-'), x = -x; char s[24]; int n = 0; while (x || !n) s[n++] = '0' + x % 10, x /= 10; while (n--) wchar(s[n]); wchar(' '); } inline void wstring(const char *s) { while (*s) wchar(*s++); } ~FastIO() { if (wpos) fwrite(wbuf, 1, wpos, stdout), wpos = 0; } } io; const int N = 3e6 + 10; struct Node { int id, key, par, ch[2]; LL mxlf, mxri, mnlf, mnri; inline bool operator < (Node & rhs) {return id < rhs.id;} inline void init(int _id, int _key, int _par) { key = _key, id = _id, par = _par, ch[0] = ch[1] = 0; } }tree[N]; inline int cartesian_build(int n) { for (int i = 1; i <= n; ++i) { int k = i-1; while(tree[k].key > tree[i].key) k = tree[k].par; tree[i].ch[0] = tree[k].ch[1]; tree[tree[i].ch[0]].par = i; tree[k].ch[1] = i; tree[i].par = k; } return tree[0].ch[1]; } LL ans = LONG_MIN, sum[N]; int n, a[N], b[N], rt; inline void dfs(int u) { tree[u].mxlf = tree[u].mnlf = sum[u-1]; tree[u].mxri = tree[u].mnri = sum[u]; if(tree[u].ch[0]) dfs(tree[u].ch[0]), tree[u].mxlf = max(tree[u].mxlf, tree[tree[u].ch[0]].mxlf), tree[u].mnlf = min(tree[u].mnlf, tree[tree[u].ch[0]].mnlf); if(tree[u].ch[1]) dfs(tree[u].ch[1]), tree[u].mxri = max(tree[u].mxri, tree[tree[u].ch[1]].mxri), tree[u].mnri = min(tree[u].mnri, tree[tree[u].ch[1]].mnri); if(tree[u].key > 0) ans = max(ans, tree[u].key*(tree[u].mxri-tree[u].mnlf)); else ans = max(ans, tree[u].key*(tree[u].mnri-tree[u].mxlf)); if(tree[u].ch[0]) tree[u].mxri = max(tree[u].mxri, tree[tree[u].ch[0]].mxri), tree[u].mnri = min(tree[u].mnri, tree[tree[u].ch[0]].mnri); if(tree[u].ch[1]) tree[u].mxlf = max(tree[u].mxlf, tree[tree[u].ch[1]].mxlf), tree[u].mnlf = min(tree[u].mnlf, tree[tree[u].ch[1]].mnlf); } int main() { n = io.xint(); for (int i = 1; i <= n; ++i) a[i] = io.xint(); tree[0].init(0, -1000001, 0); for (int i = 1; i <= n; ++i) b[i] = io.xint(), sum[i] = sum[i-1]+b[i], tree[i].init(i, a[i], 0); rt = cartesian_build(n); dfs(rt); printf("%lld ", ans); return 0; }
D
思路:$2^p\%3$:如果$p$是偶数,是1;如果$p$奇数,是2。
然后如果$a\%3==0$,答案就是本身;如果$a\% 3==1$,可以取出一个偶数位或两个奇数位,然后考虑怎把这些位和之前的位构成3的倍数;如果$a\%3==2$,同理。
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define y1 y11 #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb emplace_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pli pair<LL, int> #define pii pair<int, int> #define piii pair<pii, int> #define pdd pair<double, double> #define mem(a, b) memset(a, b, sizeof(a)) #define debug(x) cerr << #x << " = " << x << " "; #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); //head int T; LL a; vector<int> vc[2]; vector<LL> res; int main() { scanf("%d", &T); while(T--) { vc[0].clear(); vc[1].clear(); res.clear(); scanf("%lld", &a); for (int i = 0; i <= 61; ++i) { if(a&(1LL<<i)) vc[i%2].pb(i); } if(a%3 == 0) { res.pb(a); } else if(a%3 == 2) { bool f = false; if(vc[1].size() > 0) { if(vc[0].size() > 0) { int x = vc[1][0], y = vc[0][0]; res.pb(a^(1LL<<x)); res.pb((1LL<<x)|(1LL<<y)); f = true; } if(vc[1].size() >= 3) { int x = vc[1][0], y = vc[1][1], z = vc[1][2]; res.pb(a^(1LL<<x)); res.pb((1LL<<x)^(1LL<<y)^(1LL<<z)); f = true; } } if(!f && vc[0].size() >= 3) { int x = vc[0][0], y = vc[0][1], z = vc[0][2]; res.pb(a^(1LL<<x)^(1LL<<y)); res.pb((1LL<<x)^(1LL<<y)^(1LL<<z)); f = true; } } else { bool f = false; if(vc[0].size() > 0) { if(vc[1].size() > 0) { int x = vc[0][0], y = vc[1][0]; res.pb(a^(1LL<<x)); res.pb((1LL<<x)|(1LL<<y)); f = true; } if(vc[0].size() >= 3) { int x = vc[0][0], y = vc[0][1], z = vc[0][2]; res.pb(a^(1LL<<x)); res.pb((1LL<<x)^(1LL<<y)^(1LL<<z)); f = true; } } if(!f && vc[1].size() >= 3) { int x = vc[1][0], y = vc[1][1], z = vc[1][2]; res.pb(a^(1LL<<x)^(1LL<<y)); res.pb((1LL<<x)^(1LL<<y)^(1LL<<z)); f = true; } } printf("%d ", (int)res.size()); //LL t = 0; for (int i = 0; i <res.size(); ++i) printf("%lld%c", res[i], " "[i+1==res.size()]); //cout << t << endl; } return 0; }
E
思路:二维二项式反演。
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define y1 y11 #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb push_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pli pair<LL, int> #define pii pair<int, int> #define piii pair<pii, int> #define pdd pair<double, double> #define mem(a, b) memset(a, b, sizeof(a)) #define debug(x) cerr << #x << " = " << x << " "; #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); //head const int MOD = 998244353; int T, c1, c2; LL n, a, C[65][65], f[65][65]; inline LL q_pow(LL n, LL k) { LL res = 1; while(k) { if(k&1) res = (res*n)%MOD; n = (n*n)%MOD; k >>= 1; } return res; } inline void init() { C[0][0] = 1; for (int i = 1; i < 65; ++i) { C[i][0] = 1; for (int j = 1; j <= i; ++j) C[i][j] = (C[i-1][j]+C[i-1][j-1])%MOD; } for (int i = 0; i < 65; ++i) { for (int j = 0; j < 65; ++j) { for (int ii = 0; ii <= i; ++ii) { for (int jj = 0; jj <= j; ++jj) { if((ii*1+jj*2)%3 == 0) { (f[i][j] += C[i][ii]*C[j][jj]%MOD) %= MOD; } } } } } } int main() { init(); scanf("%d", &T); while(T--) { scanf("%lld %lld", &n, &a); c1 = c2 = 0; for (int i = 0; i <= 60; ++i) { if(a&(1LL<<i)) { if(i%2 == 0) ++c1; else ++c2; } } LL ans = 0; for (int i = 0; i <= c1; ++i) { for (int j = 0; j <= c2; ++j) { if((c1-i+c2-j)%2 == 0) (ans += C[c1][i]*C[c2][j]%MOD*q_pow(f[i][j], n)) %= MOD; else (ans -= C[c1][i]*C[c2][j]%MOD*q_pow(f[i][j], n)) %= MOD; } } ans = (ans + MOD) % MOD; printf("%lld ", ans); } return 0; }
F
思路:fhq treap。split操作换成按位置split。
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define y1 y11 #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb emplace_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pli pair<LL, int> #define pii pair<int, int> #define piii pair<pii, int> #define pdd pair<double, double> #define mem(a, b) memset(a, b, sizeof(a)) #define debug(x) cerr << #x << " = " << x << " "; #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); //head struct fhq_treap { static const int N = 1e5 + 5; struct Node { int val, mx, key, lc, rc, sz; }tree[N]; int rt, tot; inline void init() { rt = tot = 0; tree[rt].sz = tree[rt].val = tree[rt].mx = tree[rt].lc = tree[rt].rc = 0; srand(time(0)); } inline void update(int rt) { tree[rt].mx = max(tree[rt].val, max(tree[tree[rt].lc].mx, tree[tree[rt].rc].mx)); tree[rt].sz = tree[tree[rt].lc].sz + tree[tree[rt].rc].sz + 1; } void split(int rt, int &a, int &b, int x) { if(rt == 0) {a = b = 0; return ;} if(tree[tree[rt].lc].sz+1 <= x) { a = rt; split(tree[rt].rc, tree[a].rc, b, x-tree[tree[rt].lc].sz-1); } else { b = rt; split(tree[rt].lc, a, tree[b].lc, x); } update(rt); } void merge(int &rt, int a, int b) { if(a==0 || b==0) { rt = a+b; return ; } if(tree[a].key < tree[b].key) { rt = a; merge(tree[rt].rc, tree[a].rc, b); } else { rt = b; merge(tree[rt].lc, a, tree[b].lc); } update(rt); } inline int new_node() { tree[++tot].sz = 1; scanf("%d", &tree[tot].val); tree[tot].mx = tree[tot].val; tree[tot].lc = tree[tot].rc = 0; tree[tot].key = rand()*rand(); return tot; } void ins(int &rt) { int node = new_node(); merge(rt, rt, node); } void delete_node(int &rt, int val) { int x = 0, y = 0, z = 0; split(rt, x, y, val); split(x, x, z, val-1); merge(z, tree[z].lc, tree[z].rc); merge(x, x, z); merge(rt, x, y); } inline int get_kth(int rt, int k) { while(tree[tree[rt].lc].sz+1 != k) { if(tree[tree[rt].lc].sz >= k) rt = tree[rt].lc; else k -= tree[tree[rt].lc].sz+1, rt = tree[rt].rc; } return tree[rt].val; } int get_pos(int rt, int x) { if(!rt) return 0; if(tree[tree[rt].lc].mx > x) return get_pos(tree[rt].lc, x); else if(tree[rt].val > x) return tree[tree[rt].lc].sz; else return get_pos(tree[rt].rc, x)+tree[tree[rt].lc].sz+1; } int get_rnk(int &rt, int val) { int x = 0, y = 0; split(rt, x, y, val-1); int tmp = tree[x].sz+1; merge(rt, x, y); return tmp; } int get_pre(int &rt, int val) { int x = 0, y = 0; split(rt, x, y, val-1); int tmp = get_kth(x, tree[x].sz); merge(rt, x, y); return tmp; } int get_scc(int &rt, int val) { int x = 0, y = 0; split(rt, x, y, val); int tmp = get_kth(y, 1); merge(rt, x, y); return tmp; } }t; void solve(int l, int m, int r) { int x = 0, y = 0; t.split(t.rt, x, y, r); t.rt = x; int a = 0, b = 0; t.split(t.rt, a, b, m); t.rt = 0; while(a&&b) { int va = t.get_kth(a, 1), vb = t.get_kth(b, 1); if(va > vb) swap(va, vb), swap(a, b); int p = t.get_pos(a, vb), tmp; t.split(a, tmp, a, p); t.merge(t.rt, t.rt, tmp); } if(a) t.merge(t.rt, t.rt, a); if(b) t.merge(t.rt, t.rt, b); t.merge(t.rt, t.rt, y); } int n, m, op, l, p, r; int main() { t.init(); scanf("%d %d", &n, &m); for (int i = 1; i <= n; ++i) t.ins(t.rt); for (int i = 1; i <= m; ++i) { scanf("%d", &op); if(op == 1) { scanf("%d %d %d", &l, &p, &r); solve(l, p, r); } else { scanf("%d", &p); printf("%d ", t.get_kth(t.rt, p)); } } return 0; }
G
H
I
思路:后缀数组+回文自动机。
先将原串反转放在原来的串的后面,用后缀数组求出本质不同的串的个数$a$,然后用回文自动机求出本质不同的回文串的个数$b$,然后$frac{a+b}{2}$就是答案。
队友的板子真丑。
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define y1 y11 #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb emplace_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pli pair<LL, int> #define pii pair<int, int> #define piii pair<pii, int> #define pdd pair<double, double> #define mem(a, b) memset(a, b, sizeof(a)) #define debug(x) cerr << #x << " = " << x << " "; #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); const int maxn=4e5+10; char s[maxn]; int y[maxn],x[maxn],c[maxn],sa[maxn],rk[maxn],height[maxn]; int n,m,now,sz; int get_sa() { for (int i=0;i<=m;i++) c[i]=0; for (int i=1;i<=n;++i) ++c[x[i]=s[i]]; for (int i=2;i<=m;++i) c[i]+=c[i-1]; for (int i=n;i>=1;--i) sa[c[x[i]]--]=i; for (int k=1;k<=n;k<<=1) { int num=0; for (int i=n-k+1;i<=n;++i) y[++num]=i; for (int i=1;i<=n;++i) if (sa[i]>k) y[++num]=sa[i]-k; for (int i=1;i<=m;++i) c[i]=0; for (int i=1;i<=n;++i) ++c[x[i]]; for (int i=2;i<=m;++i) c[i]+=c[i-1]; for (int i=n;i>=1;--i) sa[c[x[y[i]]]--]=y[i],y[i]=0; swap(x,y); x[sa[1]]=1;num=1; for (int i=2;i<=n;++i) x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k]) ? num : ++num; if (num==n) break;m=num; } } int get_height() { int k=0; for (int i=1;i<=n;++i) rk[sa[i]]=i; for (int i=1;i<=n;++i) { if (rk[i]==1) continue;//第一名height为0 if (k) --k;//h[i]>=h[i-1]+1; int j=sa[rk[i]-1]; while (j+k<=n && i+k<=n && s[i+k]==s[j+k]) ++k; height[rk[i]]=k;//h[i]=height[rk[i]]; } } const double eps = 1E-8; const int dx4[4]={1,0,0,-1}; const int dy4[4]={0,-1,1,0}; const int inf = 0x3f3f3f3f; const int N=2e5+7; struct PAM { int fail,cnt,len; int nxt[26]; }st[N]; char RS[N]; string S; void pam_init() { mem(st,0); st[0].fail = st[1].fail = 1; st[1].len = -1; sz = 1; } void extend(int c,int pos) { int p = now; while (S[pos-st[p].len-1]!=S[pos]) p = st[p].fail; if (!st[p].nxt[c]){ int np=++sz,q=st[p].fail; st[np].len=st[p].len+2; while (S[pos-st[q].len-1]!=S[pos]) q=st[q].fail; st[np].fail=st[q].nxt[c]; st[p].nxt[c] = np; } now=st[p].nxt[c]; st[now].cnt++; } int main() { string ss; cin>>ss; int t=ss.size(); S=ss; ss="#"+ss+"#"; reverse(S.begin(), S.end()); ss += S; n=ss.size(); n--; for(int i=1;i<=n;i++) s[i]=ss[i]; m=122; get_sa(); get_height(); LL ans=n*1LL*(n+1)/2-1LL*(t+1)*(t+1); //cout<<ans<<endl; for(int i=1;i<=n;i++) ans-=height[i]; for(int i=0;i<=n;i++) { x[i]=0; y[i]=0; sa[i]=0; rk[i]=0; height[i]=0; } n = S.size(); pam_init(); for ( int i = 0 ; i < n; i++) extend(S[i]-'a',i); ans -= sz-1; ans /= 2; ans += sz-1; printf("%lld ",ans); }
J
思路:分层图最短路
代码:
#include <bits/stdc++.h> using namespace std; #define pb push_back #define fi first #define se second #define debug(x) cerr<<#x << " := " << x << endl; #define bug cerr<<"-----------------------"<<endl; #define FOR(a, b, c) for(int a = b; a <= c; ++ a) typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; template<class T> void _R(T &x) { cin >> x; } void _R(int &x) { scanf("%d", &x); } void _R(ll &x) { scanf("%lld", &x); } void _R(double &x) { scanf("%lf", &x); } void _R(char &x) { scanf(" %c", &x); } void _R(char *x) { scanf("%s", x); } void R() {} template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); } template<typename T> inline T read(T&x){ x=0;int f=0;char ch=getchar(); while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x=f?-x:x; } const int inf = 0x3f3f3f3f; const ll inff = 0x3f3f3f3f3f3f3f3f; const int mod = 998244353; /**********showtime************/ const int maxn = 1e3+9; vector<pii> mp[maxn]; int dis[maxn][maxn]; int n,m,s, t, k; void bfs(int s) { memset(dis, inf, sizeof(dis)); dis[s][0] = 0; queue<pii>que; que.push(pii(s, 0)); while(!que.empty()){ int u = que.front().fi; int tk = que.front().se; que.pop(); for(pii p : mp[u]) { int v = p.fi, w = p.se; if(tk < k && dis[v][tk+1] > dis[u][tk]) { dis[v][tk+1] = dis[u][tk]; que.push(pii(v, tk+1)); } if(dis[v][tk] > dis[u][tk] + w) { dis[v][tk] = dis[u][tk] + w; que.push(pii(v, tk)); } } } } int main(){ scanf("%d%d%d%d%d", &n, &m, &s, &t, &k); for(int i=1; i<=m; i++) { int u,v,w; scanf("%d%d%d", &u, &v, &w); mp[u].pb(pii(v, w)); mp[v].pb(pii(u, w)); } bfs(s); int ans = inf; for(int i=0; i<=k; i++) { ans = min(ans, dis[t][i]); } printf("%d ", ans); return 0; }
K
思路:枚举最后两个零,看前面有多少个后缀$mod3$等于0。对于$"00"$和$"0"$的情况,最后统计。
代码:
#include<bits/stdc++.h> using namespace std; const int maxn=1000000; int dp[maxn][20]; char ss[maxn]; int main(){ string ss; cin>>ss; ss="#"+ss; int l=ss.size(); long long ans=0; for(int i=1;i<=l;i++){ int x=ss[i]-'0'; dp[i][x%3]++; for(int j=0;j<=2;j++){ dp[i][(j*10+x)%3]+=dp[i-1][j]; } if(i+2 <= l){ if(ss[i+1]=='0'&&ss[i+2]=='0'){ ans += dp[i][0]; } } } for (int i = 1; i <= l; ++i) { if(ss[i] == '0') ans++; if(i-1 >= 1 && ss[i-1] == '0' && ss[i] == '0') ans++; } cout<<ans<<endl; }
题号 | 标题 | 团队的状态 |
---|---|---|
A | digits 2 | 通过 |
B | generator 1 | 通过 |
C | generator 2 | 通过 |
D | generator 3 | 未通过 |
E | independent set 1 | 通过 |
F | maximum clique 1 | 通过 |
G | subsequence 1 | 通过 |
H | subsequence 2 | 通过 |
I | three points 1 | 通过 |
J | three points 2 | 未通过 |
A
思路:输出n个n。
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define y1 y11 #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb emplace_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pli pair<LL, int> #define pii pair<int, int> #define piii pair<pii, int> #define pdd pair<double, double> #define mem(a, b) memset(a, b, sizeof(a)) #define debug(x) cerr << #x << " = " << x << " "; #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); //head int T, n; int main() { scanf("%d", &T); while(T--) { scanf("%d", &n); for (int i = 1; i <= n; ++i) printf("%d", n); printf(" "); } return 0; }
B
思路:十进制快速幂。
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define y1 y11 #define fi first #define se second #define pi acos(-1.0) #define LL long long #define ll long long //#define mp make_pair #define pb emplace_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pli pair<LL, int> #define pii pair<int, int> #define piii pair<pii, int> #define pdd pair<double, double> #define mem(a, b) memset(a, b, sizeof(a)) #define debug(x) cerr << #x << " = " << x << " "; #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); const int maxn=1e6+10; //head int MOD; struct Matrix { int a[2][2]; void init() { for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) a[i][j] = 0; } } void _init() { init(); for (int i = 0; i < 2; i++) a[i][i] = 1; } }; Matrix mul(Matrix a, Matrix b) { Matrix ans; ans.init(); for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) { if(a.a[i][j]) { for (int k = 0; k < 2; k++) ans.a[i][k] = (ans.a[i][k] + 1LL * a.a[i][j] * b.a[j][k]) % MOD; } } } return ans; } Matrix q_pow(Matrix a) { Matrix ans; ans._init(); a = mul(a, a); ans = mul(ans, a); a = mul(a, a); a = mul(a, a); ans = mul(ans, a); return ans; } char ss[maxn]; int main() { int x0,x1,a,b; scanf("%d %d %d %d",&x0,&x1,&a,&b); scanf("%s",ss); scanf("%d",&MOD); Matrix c; c.init(); c.a[0][0]=a; c.a[0][1]=b; c.a[1][0]=1; c.a[1][1]=0; Matrix d; d.init(); d.a[0][0]=x1; d.a[0][1]=0; d.a[1][0]=x0; d.a[1][1]=0; Matrix x[10]; for (int i = 0; i < 10; ++i) { if(i == 0) x[i]._init(); else x[i] = mul(x[i-1], c); } c._init(); int l = strlen(ss); for (int i = 0; i < l; ++i) { c = q_pow(c); c = mul(c, x[ss[i]-'0']); } c=mul(c,d); printf("%d ",c.a[1][0]%MOD); return 0; }
C
思路:BSGS。需要预处理。
队友代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> //#define int long long #define ll long long #define LL long long using namespace std; int x,a,b; int p,mod,MOD; int quick(int x,int n){ int ans=1; while(n){ if(n&1) ans=1ll* ans*x%mod; x=1ll*x*x%mod; n=n/2; } return ans; } struct Hash { static const int MOD = 1999997; static const int N = 1e6; int head[MOD + 10], nx[N], top; int hs[N], id[N]; void init() { memset(head, -1, sizeof head); top = 0; } void insert(int x, int y) { int k = x % MOD; hs[top] = x; id[top] = y; nx[top] = head[k]; head[k] = top++; } int find(int x) { int k = x % MOD; for (int i = head[k]; i != -1; i = nx[i]) { if (hs[i] == x) { return id[i]; } } return -1; } }hs; void init(int a,int p){ int m = pow(p,2.0/3.0)+1, s = 1; //cout<<m<<endl; hs.init(); for(int i = 0; i < m; ++i){ hs.insert(s,i); s= (s*1LL*a)%p; } } int BSGS(int a, int b, int p){ int m = pow(p,2.0/3.0)+1, s = b; int t = quick(a, m); int ww=quick(b,mod-2); s = 1; for(int i = 1; i <= p/m+1; ++i){ s = (s*1LL*t)%p; if(hs.find(1ll*s*ww%mod) != -1 ) return i*m-hs.find(1ll*s*ww%mod); } return -1; } int32_t main(){ int T; scanf("%d",&T); while(T--){ ll n; scanf("%lld %d %d %d %d",&n,&x,&a,&b,&p); mod=p; MOD=p; int q; scanf("%d",&q); init(a,p); while(q--){ ll y; scanf("%lld",&y); if(y==x) { printf("0 "); continue; } if(a==0) { // x b b b b b if(y==b) printf("1 "); else printf("-1 "); } else if(a==1){ // x+b x+2*b y=((y-x)%mod+mod)%mod; //cout<<y<<endl; y=y*quick(b,mod-2)%mod; if(1<=y && y<n ) printf("%lld ",y); else printf("-1 "); } else { //cout<<"---------"<<endl; y=( 1ll*(a-1)*y%mod+b)%mod*quick( (1ll*(a-1)*x%mod+b)%mod,mod-2)%mod; y=BSGS(a,y,p); if(1<=y && y<=n ) printf("%lld ",y); else printf("-1 "); } } } }
D
E
思路:状压dp。有两个优化的地方,用char开数组优化空间,从最低位转移优化时间。
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define y1 y11 #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb emplace_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pli pair<LL, int> #define pii pair<int, int> #define piii pair<pii, int> #define pdd pair<double, double> #define mem(a, b) memset(a, b, sizeof(a)) #define debug(x) cerr << #x << " = " << x << " "; #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); //head vector<int> g[26]; int n, m, u, v, st[26]; char dp[(1<<26)+10], mp[(1<<26)+10]; int main() { scanf("%d %d", &n, &m); for (int i = 0; i < m; ++i) { scanf("%d %d", &u, &v); st[u] |= 1<<v; st[v] |= 1<<u; } for (int i = 0; i < n; ++i) st[i] |= 1<<i; int p = 1; for (int i = 0; i < n; ++i) mp[p] = i, p <<= 1; dp[0] = 0; int up = 1<<n, ans = 0; for (int i = 1; i < up; ++i) { int x = i&-i; dp[i] = max(dp[i], dp[i^x]); dp[i] = max(dp[i], (char)(dp[i&(~st[mp[x]])]+1)); ans += dp[i]; } printf("%d ", ans); return 0; }
F
思路:最大团转换成二分图最大独立集。
队友代码:
// #pragma GCC optimize(2) // #pragma GCC optimize(3) // #pragma GCC optimize(4) #include <algorithm> #include <iterator> #include <iostream> #include <cstring> #include <cstdlib> #include <iomanip> #include <bitset> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <stack> #include <cmath> #include <queue> #include <list> #include <map> #include <set> #include <cassert> // #include<bits/extc++.h> // using namespace __gnu_pbds; using namespace std; #define pb push_back #define fi first #define se second #define debug(x) cerr<<#x << " := " << x << endl; #define bug cerr<<"-----------------------"<<endl; #define FOR(a, b, c) for(int a = b; a <= c; ++ a) typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int inf = 0x3f3f3f3f; const ll inff = 0x3f3f3f3f3f3f3f3f; const int mod = 998244353; template<typename T> inline T read(T&x){ x=0;int f=0;char ch=getchar(); while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x=f?-x:x; } /**********showtime************/ const int maxn = 5e3+9; int a[maxn]; int col[maxn]; vector<int>L, R; vector<int>mp[maxn]; void dfs(int s, int c) { col[s] = c; for(int i=0; i<mp[s].size(); i++){ int v = mp[s][i]; if(col[v] == 0) dfs(v, 3 - c); } } int vis[maxn],match[maxn],pt[maxn]; bool gkd(int u) { if(vis[u]) return false; vis[u] = true; for(int i = 0; i<mp[u].size(); i++) { int v = mp[u][i]; if(match[v] == -1 || gkd(match[v]) ){ match[v] = u; pt[u] = v; return true; } } return false; } int res[maxn]; bool findmn(int u) { if(u == -1) return false; if(res[u]) return true; // res[u] = 1; if(col[u] == 1){ if(findmn(pt[u])) {res[u] = 1;return true;} else return false; } else { res[u] = 1; for(int i=0; i<mp[u].size(); i++) { int v = mp[u][i]; if(match[u] == v) continue; findmn(v); } return true; } } int main(){ int n; scanf("%d", &n); for(int i=1; i<=n; i++) scanf("%d", &a[i]); for(int i=1; i<=n; i++) { for(int j=i+1; j<=n; j++) { if(__builtin_popcount(a[i] ^ a[j]) == 1) { mp[i].pb(j); mp[j].pb(i); } } } for(int i=1; i<=n; i++) if(col[i] == 0) dfs(i, 1); int cnt = 0; memset(match, -1, sizeof(match)); for(int i=1; i<=n; i++) { memset(vis, 0, sizeof(vis)); if(col[i] == 1 && gkd(i)) cnt++; } printf("%d ", n-cnt); for(int i=1; i<=n; i++) { if(col[i] == 2 && match[i] == -1) {findmn(i);} } vector<int>ans; for(int i=1; i<=n; i++) { if(col[i] == 1 && res[i] == 0) ans.pb(a[i]); if(col[i] == 2 && res[i] == 1) ans.pb(a[i]); } for(int i=0; i<ans.size(); i++) { printf("%d ", ans[i]); } puts(""); return 0; }
G
思路:dp。
代码:
#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn=3e3+10; const int mod=998244353; int dp[maxn][maxn]; char ss[maxn]; char tt[maxn]; int A[maxn]; int B[maxn]; int quick(int x,int n){ int ans=1; while(n){ if(n&1) ans=1ll*ans*x%mod; x=1ll*x*x%mod; n=n/2; } return ans; } int C(int n,int x){ if(x>n) return 0; return 1ll*A[n]*B[n-x]%mod*B[x]%mod; } int main(){ A[0]=1; B[0]=1; for(int i=1;i<maxn;i++) A[i]=1ll*A[i-1]*i%mod; for(int i=1;i<maxn;i++) B[i]=quick(A[i],mod-2); //cout<<1ll*121321*1354534<<endl; int T; scanf("%d",&T); while(T--){ int ans=0; int n,m; scanf("%d %d",&n,&m); scanf("%s",ss+1); scanf("%s",tt+1); dp[0][0]=1; for(int i=1;i<=n;i++){ if(ss[i]!='0'){ for(int j=m;j<=n-i;j++){ ans+=C(n-i,j); ans=ans%mod; } } for(int j=0;j<=m-1;j++) dp[i][j]=dp[i-1][j]; for(int j=0;j<=m-1;j++){ if(ss[i]==tt[j+1]) { dp[i][j+1]+=dp[i-1][j]; dp[i][j+1]%=mod; } else if(ss[i]>tt[j+1]){ ans+=1ll*dp[i-1][j]*C(n-i,m-j-1)%mod; ans=ans%mod; } } } printf("%d ",ans); for(int i=0;i<=n+1;i++){ for(int j=0;j<=m+1;j++){ dp[i][j]=0; } } } return 0; }
H
思路:拓扑排序。
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include <bits/stdc++.h> using namespace std; #define pb push_back #define fi first #define se second #define debug(x) cerr<<#x << " := " << x << endl; #define bug cerr<<"-----------------------"<<endl; #define FOR(a, b, c) for(int a = b; a <= c; ++ a) typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; template<typename T> inline T read(T&x){ x=0;int f=0;char ch=getchar(); while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x=f?-x:x; } const int inf = 0x3f3f3f3f; const ll inff = 0x3f3f3f3f3f3f3f3f; const int mod = 998244353; /**********showtime************/ const int maxn = 1e4+9; int vis[22], visno[22]; char str[5]; char res[maxn]; int tot = 0; vector<int> mp[22]; vector<int>G[maxn*100]; int pt[maxn*100]; int du[maxn*100]; int id[maxn]; char ans[maxn]; int main(){ int n,m; scanf("%d%d", &n, &m); int cnt = m * (m - 1) / 2; int flag = 1; memset(vis, -1, sizeof(vis)); for(int i=1; i<=cnt; i++) { scanf("%s", str); int len; scanf("%d", &len); if(len == 0) { int dd1 = str[0] - 'a'; int dd2 = str[1] - 'a'; visno[dd1] = visno[dd2] = 1; continue;/// } scanf("%s", res); int dd1 = str[0] - 'a'; int dd2 = str[1] - 'a'; if(vis[dd1] == -1) { int cc = 0; for(int j = 0; j<len; j++) { if(res[j] == str[0]) { id[j] = ++tot; mp[dd1].pb(tot); pt[tot] = dd1; cc++; } } vis[dd1] = cc; } else { int cc = 0; for(int j=0; j<len; j++) { if(res[j] == str[0]) { if(cc < mp[dd1].size()) id[j] = mp[dd1][cc]; cc++; } } if(cc != vis[dd1])flag = 0; } if(vis[dd2] == -1) { int cc = 0; for(int j = 0; j<len; j++) { if(res[j] == str[1]) { id[j] = ++tot; mp[dd2].pb(tot); pt[tot] = dd2; cc++; } } vis[dd2] = cc; } else { int cc = 0; for(int j=0; j<len; j++) { if(res[j] == str[1]) { if(cc < mp[dd2].size()) id[j] = mp[dd2][cc]; cc++; } } if(cc != vis[dd2])flag = 0; } for(int j=0; j<len-1; j++) { G[id[j]].pb(id[j+1]); du[id[j+1]]++; } } for(int i=0; i<m; i++) { if(vis[i] && visno[i]) flag = 0; } if(!flag || tot != n) puts("-1"); else { // string ans = ""; int all = 0; queue<int>que; for(int i=1; i<=tot; i++) if(du[i] == 0) que.push(i); while(!que.empty()) { int u = que.front(); que.pop(); // ans += pt[u] +'a'; ans[all++] = pt[u] + 'a'; for(int i=0; i<G[u].size(); i++) { int v = G[u][i]; du[v]--; if(du[v] == 0) { que.push(v); } } } int ff = 1; for(int i=1; i<=tot; i++) if(du[i] > 0) ff = 0; if(ff == 0) puts("-1"); else { ans[all] = '