文章目录
B 智乃买瓜 dpC 智乃买瓜h dpE 智乃的数字积木(easy version) 暴力模拟F 智乃的数字积木(hard version) 【待补G 智乃的树旋转(easy version) 思维H 智乃的树旋转(hard version) 【待补I 智乃的密码 尺取/二分J 智乃的C语言模除方程 分类讨论 【待补K 智乃的C语言模除方程(another version) 【待补总结
比赛链接
B 智乃买瓜 dp
题目链接
题意：
(
1
<
=
n
<
=
1
e
3
,
1
<
a
i
<
=
1
e
3
)
(1<=n<=1e3,1(1<=n<=1e3,1
题解：
#include
#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<
C 智乃买瓜h dp
题目链接
题意：
题解：
i的方案数 等于 i自己的个数 + 其他组合的和等于i 的方案数
i自己的个数 等于 i的方案数 - 其他组合的和等于i 的方案数
i的方案数已知
其他组合的和等于i的方案数就是背包过来的
#include
using namespace std;
#define int long long
const int N=1e6+5;
const int M=1e9+7;
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);
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;
}
}
num[i]=p;
cnt+=num[i];
}
if(cnt) {
cout<
E 智乃的数字积木(easy version) 暴力模拟
题目链接
题意：
题解：
#include
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 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>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()), ks=i;
}
int o=0;
for(int i=1; i<=n; i++) {
o=o*10+a[i];
o%=M;
}
cout<>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()), ks=i;
}
int o=0;
for(int i=1; i<=n; i++) {
o=o*10+a[i];
o%=M;
}
cout<
F 智乃的数字积木(hard version) 【待补
题目链接
题意：
题解：
G 智乃的树旋转(easy version) 思维
题目链接
题意：
题解：
父亲-儿子 ->儿子-父亲
#include
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<
H 智乃的树旋转(hard version) 【待补
题目链接
题意：
题解：
I 智乃的密码 尺取/二分
题目链接
题意：
题解：
二分一个对于 i 开始在[L, R]之内的最小合法解
尺取的话每次找到合法的的解 ans+=R-当前长度
#include
#define int long long
using namespace std;
const int N=1e6+7;
const int maxn=1100;
int n, m;
int L, R;
int sum[N][10];
string s;
signed main() {
cin>>n>>L>>R;
cin>>s;s=','+s;
for(int i=1;i<=n;i++) {
for(int j=1; j<=4; j++) sum[i][j]=sum[i-1][j];
if(s[i]>='A'&&s[i]<='Z') sum[i][1]++;
else if(s[i]>='a'&&s[i]<='z') sum[i][2]++;
else if(s[i]>='0'&&s[i]<='9') sum[i][3]++;
else sum[i][4]++;
}
int ans=0;
for(int i=1;i<=n-L+1;i++) {
int l=i+L-1, r=min(i+R-1, n);
int res=-1;
while(l<=r) {
int mid=(l+r)/2;
if(min(1ll, sum[mid][1]-sum[i-1][1])+min(1ll,sum[mid][2]-sum[i-1][2])+min(1ll,sum[mid][3]-sum[i-1][3])+min(1ll,sum[mid][4]-sum[i-1][4])>=3) {
r=mid-1;
res=mid;
}else {
l=mid+1;
}
}
if(res!=-1) {
ans+=min(i+R-1, n)-res+1;
}
}
cout<
J 智乃的C语言模除方程 分类讨论 【待补
题目链接
题意：
题解：
K 智乃的C语言模除方程(another version) 【待补
题目链接
总结
Qwq
