本文作者:qyh 本文分类:编程学习笔记 浏览:588
阅读时间:8059字, 约9-13.5分钟
题解是我“氪金”弄来的,勿外传。。否则会被官方封号的
注意:Div1的同学是CDEF四道题目,Div2的同学是ABCD四道题目。
A题:可持久化动态仙人掌的直径问题(雾)
题解思路:

本题代码(简单到爆,,,所以叫签到题)
#include<bits/stdc++.h> int n,m; int main(){ scanf("%d%d",&n,&m); printf("%d",(int)(pow(n,1.0/m)+1e-12)); return 0; }
Continue to next page....
B题:混凝土数学
题解思路:

本题代码:
#include<bits/stdc++.h> using namespace std; #define FL(a) {freopen(a".in","r",stdin);freopen(a".out","w",stdout);} #define Mod 998244353 #define int long long const int mx=200000; int n,a,tax[200005],sum[200005]; const int inv2=(Mod+1)/2,inv3=(Mod+1)/3,inv6=inv2*inv3%Mod; signed main(){ // FL("data1-1"); scanf("%lld",&n); for(int i=1;i<=n;++i){ scanf("%lld",&a); tax[a]++; } int ans=0; for(int i=1;i<=mx;++i)sum[i]=(sum[i-1]+tax[i])%Mod; for(int i=1;i<=mx;++i){ int N=tax[i]; if(N<2)continue; // cerr<<"N: "<<N<<endl; ans=(ans+N*(N-1)/2%Mod*(sum[min(i*2-1,mx)]-N)%Mod+N*(N-1)%Mod*(N-2)%Mod*inv6%Mod)%Mod; } printf("%lld\n",ans); cerr<<"ans: "<<ans<<endl; return 0; }
C题:论如何玩转 Excel 表格
思路:

代码:
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<queue> #include<stack> #include<vector> #include<map> using namespace std; const int maxn = 2e6+10; int read(){ int x=0,f=1; char c=getchar(); while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} while(isdigit(c)){x=(x<<3)+(x<<1)+c-48;c=getchar();} return x*f; } int k,m,n; int a[maxn],b[maxn],c[maxn],d[maxn],fa[maxn],p[maxn]; pair<int,int> P[maxn]; int sum[maxn]; void add(int x){for(int i=x;i<=n;i+=i&-i)sum[i]++;} int query(int x){int SUM=0;for(int i=x;i;i-=i&-i)SUM+=sum[i];return SUM;} int main(){ n=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=n;i++)b[i]=read(); for(int i=1;i<=n;i++){c[i]=read();P[c[i]]=make_pair(i,1);} for(int i=1;i<=n;i++){d[i]=read();P[d[i]]=make_pair(i,2);} for(int i=1;i<=n;i++){fa[a[i]]=b[i];fa[b[i]]=a[i];} for(int i=1;i<=n;i++){ if(fa[c[i]]!=d[i] || fa[d[i]]!=c[i]){puts("dldsgay!!1");return 0;} if((P[a[i]].first+P[a[i]].second)%2!=(i+1)%2){puts("dldsgay!!1");return 0;} if((P[b[i]].first+P[b[i]].second)%2!=(i+2)%2){puts("dldsgay!!1");return 0;} } for(int i=1;i<=n;i++)p[a[i]]=i; for(int i=1;i<=n;i++)c[i]=p[c[i]]+p[d[i]]; long long ans=0; for(int i=n;i>=1;i--){ ans+=query(c[i]); add(c[i]); } printf("%lld\n",ans); return 0; }
D题:可重集
思路:

代码:
#include<bits/stdc++.h> using namespace std; #define int long long #define INT __int128 #define ULL unsigned long long int read(){ int a=0;char c=getchar(); while(c>'9'||c<'0')c=getchar(); while('0'<=c&&c<='9'){ a=a*10+c-48; c=getchar(); } return a; } int MUL(int a,int x,int Mod){ // return (INT)a*x%Mod; int ans=0,w=a; while(x){ if(x&1)ans=(ans+w)%Mod; w=(w+w)%Mod; x>>=1; } return ans; } const int G1=1145141; const int MMod=1000000000000000003ll; #define MN 2000005 #define Ls (x<<1) #define Rs (x<<1|1) #define mid ((l+r)>>1) #define piii pair<int,int> #define mp make_pair #define x first #define y second int aupd(int a){return (a<MMod)?a:(a-MMod);} int supd(int a){return (a>=0)?a:(a+MMod);} int pw1[MN],s1[MN]; int sum[MN]; int n,q,a[MN]; void build(){ for(int i=1;i<=n;++i){ s1[i]=aupd(s1[i]+pw1[a[i]]); sum[i]=sum[i]+a[i]; int to=i+(i&(-i)); s1[to]=aupd(s1[to]+s1[i]); sum[to]=sum[to]+sum[i]; } } void add(int x,int v1,int v2){ while(x<=n){ s1[x]=aupd(s1[x]+v1); sum[x]+=v2;x+=x&(-x); } } piii ask(int x){ piii res=mp(0,0); while(x){ res.x=aupd(res.x+s1[x]); res.y+=sum[x]; x-=x&(-x); } return res; } piii qry(int l,int r){ piii R=ask(r),L=ask(l-1); R.x=supd(R.x-L.x); R.y-=L.y; return R; } signed main(){ n=read();q=read(); pw1[0]=1; for(int i=1;i<=1000000;++i){ pw1[i]=MUL(pw1[i-1],G1,MMod); } for(int i=1;i<=n;++i){ a[i]=read(); } build(); for(int i=1;i<=q;++i){ int op=read(); if(!op){ int x=read(),y=read(); add(x,supd(pw1[y]-pw1[a[x]]),y-a[x]); a[x]=y; } else{ int l1=read(),r1=read(),l2=read(),r2=read(),len=r1-l1+1; piii res1=qry(l1,r1),res2=qry(l2,r2); int k=res2.y-res1.y; if(abs(k)%len!=0){puts("NO");continue;} k/=len; if(k>=0){ res1.x=MUL(res1.x,pw1[k],MMod); } else { k=-k; res2.x=MUL(res2.x,pw1[k],MMod); } if(res1.x==res2.x)puts("YES"); else puts("NO"); } } return 0; }
E题:序列
思路:

代码:
#include<bits/stdc++.h> using namespace std; template<typename T>inline T read(){ T f=0,x=0;char c=getchar(); while(!isdigit(c)) f=c=='-',c=getchar(); while(isdigit(c)) x=x*10+c-48,c=getchar(); return f?-x:x; } namespace run{ const int N=5009,mod=998244353; inline int add(int x,int y){return x+y>=mod?x-mod+y:x+y;} inline int sub(int x,int y){return x>=y?x-y:x+mod-y;} inline int qpow(int x,int y){ int ret=1; while(y){ if(y&1) ret=1LL*x*ret%mod; x=1LL*x*x%mod,y>>=1; } return ret; } int fac[N],ifac[N]; inline int C(int n,int m){ if(n<0 || m<0 || n<m) return 0; return 1LL*fac[n]*ifac[m]%mod*ifac[n-m]%mod; }inline int calc(int n,int d,int m){return sub(C(n,n-d-m),C(n,n-d-m+1));} int f[N][N],n,k,inv; int main(){ n=read<int>(),k=read<int>(),inv=qpow(n,mod-2); fac[0]=ifac[0]=ifac[1]=1; for(int i=1;i<=n;i++) fac[i]=1LL*fac[i-1]*i%mod; ifac[n]=qpow(fac[n],mod-2); for(int i=n-1;i>=1;i--) ifac[i]=1LL*ifac[i+1]*(i+1)%mod; assert(1LL*fac[n-1]*ifac[n-1]%mod==1); f[0][0]=1; for(int i=1;i<=k;i++){ int sum=f[i-1][n]; for(int j=min(n,i);j;j--){ sum=(1LL*sum*j%mod*inv+f[i-1][j-1])%mod; f[i][j]=1LL*inv*(n-j+1)%mod*sum%mod; } } int chk=0; for(int i=0;i<=n;i++) chk=add(chk,f[k][i]); assert(chk==1); for(int i=1;i<=n;i++) f[k][i]=1LL*f[k][i]*qpow(C(n,i),mod-2)%mod; int ans=0; for(int i=1;i<=n;i++) for(int j=2;j<=n && min(i,n-i)>=j/2;j+=2) ans=(1LL*f[k][i]*calc(n,i,(j-2*i)/2)%mod*j+ans)%mod; printf("%d\n",ans); return 0; } } int main(){ #ifdef my freopen("sequence.in","r",stdin); freopen("sequence.out","w",stdout); #endif return run::main(); }
F题:一次函数
思路:

代码:
#include <bits/stdc++.h> using namespace std; const int Maxi = 1030, Maxn = 20005; int n, m, ct, bloc, f[Maxn][Maxi], pos[Maxi], fac[Maxi]; pair <int, int> from[Maxn][Maxi]; long long d, p, goal, val[Maxn], arr[Maxn]; pair <int, long long> ans[Maxn]; map <int, int> Ma; typedef pair <long long, long long> pll; pll G; pll operator * (const pll &x, const pll &y) { return make_pair((x.first * y.second + x.second * y.first) % p, x.second * y.second % p); } long long gcd(long long x, long long y) { return x == 0 ? y : gcd(y % x, x); } long long fast_pow(long long x, long long y) { long long ans = 1, now = x; while (y) { if (y & 1) ans = ans * now % p; now = now * now % p; y >>= 1; } return ans; } pll fast_pow(pll x, long long y) { pll ans = make_pair(0, 1), now = x; while (y) { if (y & 1) ans = ans * now; now = now * now; y >>= 1; } return ans; } void dp(void) { int maxi = (1 << ct) - 1; memset(f, 0x3f, sizeof(f)); f[0][maxi] = 0; for (int i = 1; i <= n; i++) { int sta = 0; long long tmp_val = val[i] / gcd(val[i], goal); for (int j = 1; j <= ct; j++) if (tmp_val % fac[j] == 0) sta |= 1 << (j - 1); for (int j = 1; j <= maxi; j++) if (f[pos[j]][j] + 1 < f[pos[j & sta]][j & sta]) { pos[j & sta] = i; f[i][j & sta] = f[pos[j]][j] + 1; from[i][j & sta] = make_pair(pos[j], j); } } } int get_unit(void) { int maxi = sqrt(p - 1); for (int i = 2; ; i++) { for (int j = 2; j <= maxi; j++) if ((p - 1) % j == 0) { if (fast_pow(i, j) == 1) goto END; if (fast_pow(i, (p - 1) / j) == 1) goto END; } return i; END:; } } void get_factor(void) { int maxi = sqrt(p - 1), tmp = p - 1; for (int i = 2; i <= maxi; i++) if (tmp % i == 0) { fac[++ct] = i; while (tmp % i == 0) tmp /= i; } if (tmp != 1) fac[++ct] = tmp; fac[++ct] = p; } pll exgcd(long long x, long long y) { if (!x) return make_pair(0, 1); else { pll tmp = exgcd(y % x, x); return make_pair(tmp.second - tmp.first * (y / x), tmp.first); } } long long mod(__int128 x) { return (x % (p * (p - 1)) + (p * (p - 1))) % (p * (p - 1)); } void work(int lt, long long goal_now) { long long g = p * (p - 1), div = gcd(goal_now, p * (p - 1)); for (int i = lt + 1; i <= m; i++) g = gcd(g, arr[i]); div = gcd(g, arr[lt]); arr[lt] /= div, g /= div, goal_now /= div; pll result = exgcd(arr[lt], g); ans[lt].second = mod((__int128) result.first * goal_now); if (lt == m - 1) { ans[m].second = mod((__int128) result.second * goal_now); return ; } work(lt + 1, mod(mod((__int128) result.second * goal_now) * (__int128) g)); } void BSGS_init(void) { bloc = sqrt(n * p); long long now = 1; d = get_unit(); for (int i = 0; i < bloc; i++) { Ma[now] = i; now = now * d % p; } } long long BSGS(pll val_now) { long long inv = fast_pow(fast_pow(d, bloc), p - 2), now_inv = 1; for (int j = 0; j < p / bloc + 1; j++) { if (Ma[now_inv * val_now.second % p]) { long long tmp = Ma[now_inv * val_now.second % p] + j * (long long) bloc; pll tmp_val = val_now * fast_pow(make_pair(1, d), p * (p - 1) - tmp); return ((p - 1) * (p - tmp_val.first * d % p) + tmp) % (p * (p - 1)); } (now_inv *= inv) %= p; } } int main() { scanf("%d%lld%lld%lld", &n, &p, &G.first, &G.second); BSGS_init(); get_factor(); goal = BSGS(G); long long g = gcd(p * (p - 1), goal); for (int i = 1; i <= n; i++) { pll x; scanf("%lld%lld", &x.first, &x.second); val[i] = BSGS(x), g = gcd(g, val[i]); } for (int i = 1; i <= n; i++) val[i] /= g; dp(); if (f[pos[0]][0] > n) { puts("-1"); return 0; } pair <int, int> now = make_pair(pos[0], 0); while (now.first) { arr[++m] = val[now.first]; ans[m].first = now.first; now = from[now.first][now.second]; } work(1, goal); printf("%d\n", m); for (int i = 1; i <= m; i++) printf("%d %lld\n", ans[i].first, ans[i].second); return 0; }
希望对大家有所帮助。
关于作者qyh
- 还没有填写个人简介
- Email: qinyihao071206@gmail.com
- 注册于: 2020-04-07 01:29:40
A : 签到题,没啥思维难度,怕 math 库掉精度,直接暴力枚举莽了(这题目名是咋回事,,,)。
B : 简单的 cf 风格组合数学题,个人感觉质量一般。
C : 套路题,这个转逆序对套树状数组的套路不知到见过多少次了。更加不爽的是这题还卡常,网上搬了快读板子才过,没啥意思。
D : 数据结构题,我太菜了,并没做出来。试图用树状数组维护方差乱搞结果只拿到 25 分 (upd 貌似正解就是哈希乱搞,如果是这样,那这类似的 idea 也出现过无数次了吧)?
E : 概率 DP,O (n^2k) 的 DP 思路还是很好想,但是优化到 O (nk) 我并不会。然后这个 DP 超级难调,而且有点卡常,60 变 45。
F : 没看。
555 我只看懂了前两题 阿尔卑微
太 难 了
A题直接输出floor(pow(n,1/m))不就好了吗?
@Alex172 难道不香吗
@Alex172 我直接copy的
我141比qyh高10分
@Zhang, Xuheng 雾
@Zhang, Xuheng 我156.。。
@Zhang, Xuheng 我也。
悲。
https://www.luogu.com.cn/blog/zxhlg/luo-gu-7-yue-yue-sai-zong-jie
这次比赛因为我有课,所以只打了大概35分钟。
T1很水,1分钟就过了。
T2我的第一反应是爆搜,结果打了个大暴力30分。
T3没有多少时间了,随便骗了subtask1~3的分数(11分)
最后:100+30+11+0=141.
总的来说,这次月赛整体难度不算高,如果我能打4h,应该(jue dui)
可以超过250分。
希望下次月赛的时候我不用上课。
@Zhang, Xuheng T2T3不是我给你的吗
T1你给我的
我Div2 288分
笑死了
@qyh
你第一条评论和你的实际得分情况不符啊,,,
@NSObject 23786 别人的,,,
收藏《洛谷月赛【LGR-073】题解》文章
点赞《洛谷月赛【LGR-073】题解》文章
收藏《洛谷月赛【LGR-073】题解》文章
点赞《洛谷月赛【LGR-073】题解》文章
收藏《洛谷月赛【LGR-073】题解》文章
点赞《洛谷月赛【LGR-073】题解》文章