目录
A
#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back
using namespace std;
const int N=2e5+10;
void solve()
{
string s;cin>>s;
if(s=="kou") s="yukari";
cout<<s<<endl;
return;
}
signed main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// freopen("1.in", "r", stdin);
int _;
// cin>>_;
// while(_--)
solve();
return 0;
}
B
#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back
using namespace std;
const int N=2e5+10;
void solve()
{
int n;cin>>n;
auto check=[&](int tar)
{
if(tar==1) return false;
rep(i,2,tar/i) if(tar%i==0) return false;
return true;
};
int ans=0;
for(int i=1;i<=n/i;++i)
{
if(n%i==0)
{
if(check(i)) ans++;
if(i==n/i) continue;
if(check(n/i)) ans++;
}
}
cout<<ans<<endl;
return;
}
signed main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// freopen("1.in", "r", stdin);
int _;
// cin>>_;
// while(_--)
solve();
return 0;
}
C
c题比较有用的应该还是得有贡献法这种思想。
#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back
using namespace std;
const int N=2e5+10;
void solve()
{
int n;cin>>n;
char c;cin>>c;
string s;cin>>s;
int ans=0;
rep(i,0,s.size()-1)
{
if(s[i]==c) ans+=min(i+1,n-i);
}
cout<<ans<<endl;
return;
}
signed main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// freopen("1.in", "r", stdin);
int _;
// cin>>_;
// while(_--)
solve();
return 0;
}
D
链表的模板。
需要注意的是这题的数据范围\(x、y给到了1e9\)不能用数组去模拟，直接用map去模拟
#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back
using namespace std;
const int N=2e5+10;
map<int,int> l,r;
void solve()
{
int q;cin>>q;
r[0]=1e9+1;l[1e9+1]=0;
auto add=[&](int now,int tar)
{
l[now]=tar;r[now]=r[tar];
l[r[tar]]=now; r[tar]=now;
};
auto remov=[&](int tar)
{
r[l[tar]]=r[tar];
l[r[tar]]=l[tar];
};
while(q--)
{
int op;cin>>op;
if(op==1)
{
int x,y;cin>>x>>y;
add(x,y);
}
else
{
int x;cin>>x;
remov(x);
}
}
int cnt=0;
for(int i=r[0];i!=1e9+1;i=r[i]) cnt++;
cout<<cnt<<endl;
for(int i=r[0];i!=1e9+1;i=r[i]) cout<<i<<' ';
return;
}
signed main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// freopen("1.in", "r", stdin);
int _;
// cin>>_;
// while(_--)
solve();
return 0;
}
E
这道题目也是一道比较经典的dp。
没看出来.
\(dp[i][j]:表示对前i个数进行操作，总和为j的最小操作次数\)
\(转移：dp[i][j]=min(dp[i][j+a[i]],dp[i][j-a[i]]+1)\)
\(初始化:dp[0][40000]=0,其余均是无穷大\)
注意这道题目有负数，可以将dp数组开成mp，但是最好不要这么去做，因为mp有个\(log\)
一般的做法是加上一个偏移量使每个数都变成正数。
#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back
using namespace std;
const int N=80010;
int dp[210][N];
void solve()
{
int n;cin>>n;
memset(dp,0x3f,sizeof(dp));
dp[0][40000]=0;
rep(i,1,n)
{
int xx;cin>>xx;
rep(j,0,80000)
{
if(j+xx>=0&&j+xx<=80000) dp[i][j]=min(dp[i][j],dp[i-1][j+xx]);
if(j-xx>=0&&j-xx<=80000) dp[i][j]=min(dp[i][j],dp[i-1][j-xx]+1);
}
}
if(dp[n][40000]>=n) cout<<-1;
else cout<<dp[n][40000]<<endl;
return;
}
signed main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// freopen("1.in", "r", stdin);
int _;
// cin>>_;
// while(_--)
solve();
return 0;
}
F
今天下午在补寒假营的题，里面有道用道第二类斯特林数的知识点还没补完，刚好这道题也是组合数学的就补一下，尽快把组合数学的知识点给补一下吧。
思路：
对于连续段的个数的枚举是少不了的因为这是答案
然后考虑对于i个连续段的情况。
我们的目标串可能是什么样的。
\(aaabbbb...aa..bba...\)
\(bbbaaab....aa..bb...\)
要么是a开头要么是b开头。然后连续若干个b连续若干个a
如果是a开头，分成i段那么a的段可能会比b多一点，因为a先出现，奇数的话就是a多，否则两者段一样多，那么a的段数用\(ca表示ca=i/2+i%2，cb=i-ca\)
考虑如何将x个a分成ca份，并且每份都不空：显然可以用隔板法
关于隔板法：隔板法
y分成cb份并且每份都不空。两者应用乘法原理相乘
b开头情况是一样的。
a、b开头是两种不同的情况，用加法原理就是段数为i的情况。
代码参考兰子哥的。
#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back
using namespace std;
const int N=2010;
int jc[N],mod=1e9+7;
void solve()
{
auto qmi=[&](int a,int b,int p)
{
int res=1;
while(b)
{
if(b&1) res=res*a%p;
b>>=1;
a=(a*a)%p;
}
return res;
};
jc[0]=1;
rep(i,1,2000) jc[i]=jc[i-1]*i%mod;
auto C=[&](int n,int m)
{
if(m<0||n-m<0||n<0) return 1ll*0;
return jc[n]*qmi(jc[m],mod-2,mod)%mod*qmi(jc[n-m],mod-2,mod)%mod;
};
int x,y;cin>>x>>y;
rep(i,1,x+y)
{
int ca=i/2;
int cb=i-ca;
ll ans=0;
ans=(ans+(C(x-1,ca-1)*C(y-1,cb-1))%mod)%mod;
swap(ca,cb);
ans=(ans+(C(x-1,ca-1)*C(y-1,cb-1))%mod)%mod;
cout<<ans<<endl;
}
return;
}
signed main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// freopen("1.in", "r", stdin);
int _;
// cin>>_;
// while(_--)
solve();
return 0;
}