B 智乃买瓜 dp
题目链接
题意:
有 $ n $ 个物品重量为 $ai$ ,可以买一整个或买一半或不买,问重量和为$1,2…m$的方案数。
$ (0<=n<=1e3,1<=m<=1e3, 2<ai<=2*1e3) $
题解:
$dp[i]$ 表示重量和为 $i$ 的方案数
转移方程为
$if(j>=a[i]) dp[j]+=dp[j-a[i]]$ $dp[j]$从 $dp[j-a[i]]$的状态转移过来
$if(j>=a[i]/2) dp[j]+=dp[j-a[i]/2]$
#include <bits/stdc++.h> #define int long long using namespace std; const int N=2e5+5; const int M=1e9+7; int a[N]; int dp[N]; signed main() { ios_base::sync_with_stdio(0), cin.tie(0); cout.tie(0); int n, m; cin>>n>>m; for(int i=1; i<=n; i++) cin>>a[i]; dp[0]=1; for(int i=1; i<=n; i++) { for(int j=m; j>=0; j--) { if(j>=a[i]) dp[j]=(dp[j]+dp[j-a[i]])%M; if(j>=a[i]/2) dp[j]=(dp[j]+dp[j-a[i]/2])%M; } } for(int i=1; i<=m; i++) { cout<<dp[i]%M<<" "; } return 0; }
|
C 智乃买瓜h dp
题目链接
题意:
知道重量和为 $1-m$的方案数,求有几个瓜怎么样的瓜。
$(0<=n<=1e3,1<=m<=1e3, 2<ai<=2*1e3)$
题解:
$dp[i]$ 表示重量和为 $i$ 的方案数
因为 $dp[1]$ 可以确定原重量为 2 的瓜的个数
$dp[2]$ 可以确定原重量为 4 的瓜的个数
$a[i]$ 等于 i自己的个数 + 其他组合的和等于i 的方案数
i自己的个数 等于 $dp[i]$ - 其他组合的和等于i 的方案数
i的方案数已知 其他组合的和等于i的方案数就是背包过来的
#include <bits/stdc++.h> using namespace std; #define int long long const int N=1e6+5; const int M=1e9+7; int in[N], inn[N]; pair<int, int> p[N]; vector<int> g; int dp[N]; int a[N]; int num[N]; signed main() { ios_base::sync_with_stdio(0), cin.tie(0); cout.tie(0); int n; cin>>n; dp[0]=1; for(int i=1; i<=n; i++) { cin>>a[i]; } int cnt=0; for(int i=2; i<=n+n; i+=2) { int p=((a[i/2]-dp[i/2]+M)%M); num[i]=p; cnt+=num[i]; for(int j=1; j<=p; j++) { for(int k=n; k>=0; k--) { if(k>=i) dp[k]=(dp[k]+dp[k-i])%M; if(k>=i/2) dp[k]=(dp[k]+dp[k-i/2])%M; } } } cout<<cnt<<endl; if(cnt) { cout<<cnt<<endl; for(int i=1; i<=n+n; i++) { for(int j=1; j<=num[i]; j++) { } } cout<<endl; return 0; }else { cout<<1<<endl; cout<<n*2+2<<endl; } return 0; }
|
E 智乃的数字积木(easy version) 暴力模拟
题目链接
题意:
题解:
k好小
按照题意模拟
既然要最大的数字 就在相同颜色的块从大到小排序
#include <bits/stdc++.h> using namespace std; #define int long long #define ll long long const int N=1e6+5; const int M=1e9+7; int a[N]; int col[N]; set<int> v; ll ksm(ll a,ll p){ll res=1;while(p){if(p&1){res=res*a%M;}a=a*a%M;p>>=1;}return res;} signed main() { ios_base::sync_with_stdio(0), cin.tie(0); cout.tie(0); int n, m, k; cin>>n>>m>>k; string s; cin>>s; for(int i=0; i<n; i++) { a[i+1]=s[i]-'0'; } for(int i=1; i<=n; i++) { cin>>col[i]; } int ks=1; for(int i=1; i<=n+1; i++) { if(col[i]==col[i-1])continue; else sort(a+ks, a+1+i-1, greater<int>()), ks=i; } int o=0; for(int i=1; i<=n; i++) { o=o*10+a[i]; o%=M; } cout<<o<<endl; while(k--) { int p, q; cin>>p>>q; ks=1; for(int i=1; i<=n; i++) if(col[i]==p) col[i]=q; for(int i=1; i<=n+1; i++) { if(col[i]==col[i-1]) continue; else sort(a+ks, a+1+i-1, greater<int>()), ks=i; } int o=0; for(int i=1; i<=n; i++) { o=o*10+a[i]; o%=M; } cout<<o%M<<endl; } return 0; }
|
F 智乃的数字积木(hard version) 【待补】
题目链接
题意:
题解:
```
#G 智乃的树旋转(easy version) 思维
**[题目链接](https:
##题意:
现在智乃有一颗尺寸大小为 $N$ 二叉树,智乃对其做了一次旋转操作将其打乱,她想让你通过一次树的旋转操作将其还原.
##题解:
父亲-儿子 ->儿子-父亲 ![在这里插入图片描述](https:
```c #include <bits/stdc++.h> using namespace std; const int N=1e6+5; int a, n, b; int in[N], inn[N]; signed main() { ios_base::sync_with_stdio(0), cin.tie(0); cout.tie(0); int n; cin>>n; for(int i=1; i<=n; i++) { int a, b; cin>>a>>b; in[a]=i; in[b]=i; } for(int i=1; i<=n; i++) { int a, b; cin>>a>>b; inn[a]=i; inn[b]=i; } for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { if(in[i]==j&&inn[j]==i) { cout<<1<<endl<<j<<endl; return 0; } } } cout<<0<<endl; return 0; }
|
H 智乃的树旋转(hard version) 【补】
题目链接
题意:
现在智乃有一颗尺寸大小为 $N$ 二叉树,智乃对其做了一次旋转操作将其打乱,她想让你通过一系列树的旋转操作将其还原。
$(1<=N<=1e3)$
题解:
问题
思考这么一个问题:如果对某一个非根节点,一直作为旋转轴进行旋转,那么最后会发生什么。
显然,最终该节点一定被转到了整棵树的根部。
想法
想法是先把两棵树转成一样的,旋转次数就是两棵树操作次数之和。
怎么转成同样一棵树呢因为旋转的话中序遍历是不变的。
就把图的先序遍历DLR变成中序遍历LDR的样子。
就是转所有的左子树转转转成父亲的右子树或者转成根为止。
#include<bits/stdc++.h> #define in long long using namespace std; const int N=2e3+5; int F[N][2]; int R[N][2], L[N][2]; int cnt=0; int ord[N]; int n; vector<int> V; stack<int> S; void get_order(int x, int t) { ord[++cnt]=x; if(L[x][t]) get_order(L[x][t], t); if(R[x][t]) get_order(R[x][t], t); } void RR(int l, int t) { int rt=F[l][t]; int f=F[rt][t]; int lc=R[l][t]; F[l][t]=f; F[rt][t]=l; F[lc][t]=rt; R[l][t]=rt; L[rt][t]=lc; if(L[f][t]==rt) L[f][t]=l; else R[f][t]=l; } void cal(int r, int t) { cnt=0; get_order(r, t); for(int i=1; i<=n; i++) { while(1) { int f=F[ord[i]][t]; if(f==0||R[f][t]==ord[i]) break; if(t==1) V.push_back(ord[i]); else S.push(f); RR(ord[i], t); } } } signed main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n; for(int j=0; j<=1; j++) for(int i=1; i<=n; i++) { int x, y; cin>>x>>y; L[i][j]=x;R[i][j]=y; if(x) F[x][j]=i; if(y) F[y][j]=i; } int r1=0,r2=0; for(int i=1; i<=n; i++) { if(F[i][0]==0) r1=i; if(F[i][1]==0) r2=i; } cal(r1, 0); cal(r2, 1); cout<<V.size()+S.size()<<endl; for(auto x:V) cout<<x<<endl; while(!S.empty()) { int x=S.top(); cout<<x<<endl; S.pop(); } return 0; }
|
I 智乃的密码 尺取/二分
题目链接
题意:
题解:
找到最远的合法的 r 计算 $[L, R]$范围内的ans
#include <bits/stdc++.h> #define int long long using namespace std; const int N=1e6+7; int cnt[5]; int tmp,k; long long ans; int cn(char a){ if(a>='0'&&a<='9')return 1; else if(a>='a'&&a<='z')return 2; else if(a>='A'&&a<='Z')return 3; else return 4; } signed main(){ int n,l,r; string s; cin>>n>>l>>r>>s; for(int i=0;i<=n-l;i++){ while(k<n&&tmp<3){ int o=cn(s[k]); if(cnt[o]==0)tmp++; cnt[o]++; k++; } int z=min(r-1+i,n-1)-max(k-1,l-1+i)+1; if(z>=0&&tmp>=3) ans+=z; cnt[cn(s[i])]--; if(cnt[cn(s[i])]==0)tmp--; } cout<<ans; }
|
J 智乃的C语言模除方程 分类讨论【补】
题目链接
题意:
$x$%$P==Q,L<=x<=R,l<=Q<=r$
求有多少个x使得方程成立
$(-1e9<=P,l,r,L,R<=1e9)$
题解:
qwq
$x>=0时$,Q的有效区间是$[0, p-1]$
$x<0时$,Q的有效区间是$[1-p, 0]$
首先[L,R]转化成[0, N]的问题
题目就变成查询 0 到 N 这段有多少数字
然后变成[0,N]内有多少个数模P在[l, r]内
然后算循环节和零头
答案就分为两个部分 一部分是 N%p的部分 另一部分是N/P 个(0~P-1)
这种区间统计的问题,边角讨论比较复杂的话,尽量别硬讨论
要么能转换成前缀的,算1到n,要么把边角单独处理了,然后把两个端点都放在舒服的位置,再去算
#include<bits/stdc++.h> #define in long long using namespace std; const int N=2e5+5; int n, l, r, L, R, p; int gi(int a, int b, int c, int d) { if(b<c||d<a) return 0; return min(d, b)-max(c, a)+1; } int query(int x) { if(x<0) return abs(x/p)*gi(1-p, 0, l, r)+gi((x%p), 0, l, r); return (x/p)*gi(0, p-1, l, r)+gi(0, x%p, l, r); } signed main() { cin>>p>>l>>r>>L>>R; p=abs(p); if(L<=0&&R>=0) cout<<query(L)+query(R)-query(0)<<endl; else if(R<0) cout<<query(L)-query(R+1)<<endl; else cout<<query(R)-query(L-1)<<endl; return 0; }
|
K 智乃的C语言模除方程(another version) 【待补】
**[题目链接#总结
Qwq