【题解/标程】2022牛客寒假算法基础集训营 1 题解+标程
题解pdf现在在群（477641458）的群文件中（更新：群满了，现在进975214176），过几天也会把题解挂到这个帖子里。
更新：题解pdf
更新：B站讲题视频
这里主要给出一些标程，来自于我或某位验题人（有的题我的代码太丑陋了，就放验题人的了），欢迎对照题解查看。
#include<bits/stdc++.h>
#define fors(i,a,b) for(int i = a; i < b; ++i)
#define ll long long
#define mid ((l+r)>>1)
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
const int maxn = 1e5+5;
int f[maxn][9];
const int mod = 998244353;
int main(){
int n; cin>>n;
f[0][0] = 1;
fors(i,1,n+1){
int x; scanf("%d", &x); x %= 9;
fors(j,0,9){
f[i][(j+x)%9] = (f[i][(j+x)%9] + f[i-1][j])%mod;
f[i][j] = (f[i][j]+f[i-1][j])%mod;
}
}
fors(i,1,9) cout<<f[n][i]<<" "; cout<<f[n][0]-1<<endl;
return 0;
}DP数组含义与题解中相同。
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define fs first
#define sc second
typedef long long ll;
typedef double db;
typedef pair pii;
int n,q,st[3][200010][21];
char s[200010];
int mod3(int x){
return (x%3+3)%3;
}
int main(){
cin>>n>>q;
scanf("%s",s+1);
rep(j,0,20){
rep(i,1,n){
if(j==0){
if(s[i]=='W'){
st[0][i][j]=st[1][i][j]=st[2][i][j]=1;
}
if(s[i]=='L'){
st[1][i][j]=st[2][i][j]=-1;
st[0][i][j]=0;
}
if(s[i]=='D'){
st[0][i][j]=st[1][i][j]=st[2][i][j]=0;
}
}
else{
int p1=i,p2=i+(1<<(j-1));
if(p2>n){
st[0][p1][j]=st[0][p1][j-1];
st[1][p1][j]=st[1][p1][j-1];
st[2][p1][j]=st[2][p1][j-1];
}
else{
st[0][p1][j]=st[0][p1][j-1]+st[mod3(0+st[0][p1][j-1])][p2][j-1];
st[1][p1][j]=st[1][p1][j-1]+st[mod3(1+st[1][p1][j-1])][p2][j-1];
st[2][p1][j]=st[2][p1][j-1]+st[mod3(2+st[2][p1][j-1])][p2][j-1];
}
}
}
}
int l,r,ans;
rep(_,1,q){
scanf("%d%d%d",&l,&r,&ans);
int pos=l;
while(pos<=r){
int j=0;
while(pos+(1<<j)-1<=r) j++;
j--;
ans+=st[ans%3][pos][j];
pos+=(1<<j);
}
printf("%d\n",ans);
}
return 0;
}st数组含义与题解相同，rep是上面宏定义的for()循环简写（希望你不是很讨厌这种写法）。
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define fs first
#define sc second
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
int n,le[110],a[110][5],res[1010],p;
int main(){
cin>>n;
rep(i,1,n){
le[i]=4;
rep(j,1,3){
scanf("%d",&a[i][j]);
if(a[i][j]) le[i]=min(le[i],j);
}
}
rep(i,1,n){
if(le[i]!=4){
int j=p;
while(res[j]!=i-le[i]) j--;
// printf("%d %d\n",i,j);
int add=3-(p-j);
rep(j,1,add) res[++p]=0;
}
res[++p]=i;
}
printf("%d\n",p-n);
return 0;
}res[]数组维护新的程序，res[i]=0表示这是一条空语句，否则res[i]=x表示这是源程序中第x条语句。
D 牛牛做数论
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll prime[20]={0,2,3,5,7,11,13,17,19,23,29,31,37,41};
ll n,t;
inline bool isP(int x){
if(x<=3) return true;
for(int i=2;i*i<=n;i++){
if(n%i==0) return false;
}
return true;
}
int main(){
cin>>t;
while(t--){
cin>>n;
assert(n!=0);
ll now=1,i=1;
if(n==1){
puts("-1");
continue;
}
while(now*prime[i]<=n){
now*=prime[i];
i++;
}
printf("%lld ",now);
while(!isP(n)){
n--;
}
printf("%lld\n",n);
}
return 0;
} #include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define fs first
#define sc second
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
int T,n,m;
int main(){
cin>>T;
while(T--){
scanf("%d%d",&n,&m);
if(m==1){
if(n==1) puts("1");
else puts("-1");
}
else{
printf("%d\n",((n-1)/(m-1)+((n-1)%(m-1)!=0))*2-1);
}
}
return 0;
}F 中位数切分
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define fs first
#define sc second
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
int T,n,m;
int a[100010];
int main(){
cin>>T;
while(T--){
scanf("%d%d",&n,&m);
int ans=0;
rep(i,1,n){
scanf("%d",&a[i]);
if(a[i]>=m) ans++;
else ans--;
}
if(ans>0) printf("%d\n",ans);
else puts("-1");
}
return 0;
}↑题解中的简单方法；
#include<bits/stdc++.h>
using ll = long long;
using ld = long double;
namespace GTI
{
char gc(void)
{
const int S = 1 << 16;
static char buf[S], *s = buf, *t = buf;
if (s == t) t = buf + fread(s = buf, 1, S, stdin);
if (s == t) return EOF;
return *s++;
}
ll gti(void)
{
ll a = 0, b = 1, c = gc();
for (; !isdigit(c); c = gc()) b ^= (c == '-');
for (; isdigit(c); c = gc()) a = a * 10 + c - '0';
return b ? a : -a;
}
int gts(char *s)
{
int len = 0, c = gc();
for (; isspace(c); c = gc());
for (; c != EOF && !isspace(c); c = gc()) s[len++] = c;
s[len] = 0;
return len;
}
int gtl(char *s)
{
int len = 0, c = gc();
for (; isspace(c); c = gc());
for (; c != EOF && c != '\n'; c = gc()) s[len++] = c;
s[len] = 0;
return len;
}
}
using GTI::gti;
using GTI::gts;
using GTI::gtl;
const int inf = 0x3f3f3f3f;
struct BIT
{
std::vector<int> f;
int n;
void init(int n)
{
this->n = n;
f.resize(n);
std::fill(f.begin(), f.end(), -inf);
}
void insert(int loc, int val)
{
if (loc == 0) f[0] = std::max(f[0], val);
else
for (int i = loc; i < n; i += i & -i)
f[i] = std::max(f[i], val);
}
int query(int loc)
{
if (loc < 0) return -inf;
int ret = f[0];
for (int i = loc; i; i -= i & -i)
ret = std::max(ret, f[i]);
return ret;
}
}tr;
const int N = 1e5 + 500;
int a[N], f[N];
int main(void)
{
for (int T = gti(); T; T--)
{
int n = gti(), m = gti();
for (int i = 1; i <= n; i++)
a[i] = (gti() >= m ? 1 : -1) + a[i - 1];
{
std::vector<int> val;
for (int i = 0; i <= n; i++)
val.push_back(a[i]);
std::sort(val.begin(), val.end());
val.erase(std::unique(val.begin(), val.end()), val.end());
for (int i = 0; i <= n; i++)
a[i] = lower_bound(val.begin(), val.end(), a[i]) - val.begin();
tr.init(val.size());
}
tr.insert(a[0], 0);
for (int i = 1; i <= n; i++)
{
f[i] = tr.query(a[i] - 1) + 1;
tr.insert(a[i], f[i]);
}
if (f[n] < 0) puts("-1");
else printf("%d\n", f[n]);
}
return 0;
}↑题解中树状数组优化dp的麻烦方法。
#include<bits/stdc++.h>
#define fors(i,a,b) for(int i = a; i < b; ++i)
#define ll long long
#define mid ((l+r)>>1)
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
int sg(int x){
if(x == 0) return 0;
if(x<0) return -1;
return 1;
}
int main(){
int T; cin>>T; assert(T <= 1e4 && T > 0);
int sumn = 0;
while(T--){
int n; scanf("%d", &n); sumn += n;
assert(n <= 1e5 && n > 0);
vector<int> f(n);
fors(i,0,n) scanf("%d", &f[i]);
vector<int> t1, t2;
vector<int> cc;
int cnt = 0;
fors(i,1,n-1){
if(f[i]>f[i-1] && f[i]>f[i+1]){
int d = f[i]-max(f[i-1], f[i+1]);
int up = max(f[i-1],f[i+1]) + d/2+1;
t1.pb(up); cc.pb(up);
}
else if(f[i] < min(f[i-1], f[i+1]) ) {
int d = min(f[i-1], f[i+1])-f[i];
int up = f[i]+(d+1)/2;
t2.pb(up); cc.pb(up);
cnt++;
}else if(min(f[i-1], f[i+1]) < f[i] && max(f[i-1], f[i+1]) > f[i] ){
int l = min(f[i-1], f[i+1]);
int r = max(f[i-1], f[i+1]);
int L = l+ (f[i]-l)/2 + 1;
int R = f[i]+(r-f[i]+1)/2;
if(L <= R) {t1.pb(L), t2.pb(R);}
}
}
for(int x:t1) cc.pb(x); for(int x:t2) cc.pb(x);
sort(all(cc)); cc.erase(unique(all(cc)), cc.end());
vector<int> d(cc.size());
for(int x:t1){
// cout<<"x1:"<<x<<endl;
int p = lower_bound(all(cc), x)-cc.begin(); d[p]++;
}
for(int x:t2){
// cout<<"x2:"<<x<<endl;
int p = lower_bound(all(cc), x)-cc.begin(); d[p]--;
}
int ans = cnt;
fors(i,1,d.size()) d[i]+=d[i-1];
for(int x:d) ans = min(ans, cnt+x);
cout<<ans<<endl;
}
assert(sumn <= 1e6 && sumn > 0);
return 0;
}这里是将题解中提到预处理出来的所有区间的
放到
中、
放到
中，然后解区间覆盖问题。
H 牛牛看云
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define fs first
#define sc second
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
int n;
int a[1000010];
ll cnt[1010];
int main(){
cin>>n;
rep(i,1,n){
scanf("%d",&a[i]);
cnt[a[i]]++;
}
ll ans=0;
rep(i,0,1000){
rep(j,i,1000){
ll add;
if(i==j) add=(cnt[i]+cnt[i]*(cnt[i]-1ll)/2ll);
else add=cnt[i]*cnt[j];
ans=ans+add*(ll)abs(i+j-1000);
}
}
printf("%lld\n",ans);
return 0;
}add表示当前的(i,j)对儿贡献了多少次。
I B站与各唱各的
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
const int P = 1000000007;
int ksm(int x,int k) {
int ans=1;
while (k) {
if (k&1) ans=1ll*ans*x%P;
x=1ll*x*x%P;
k>>=1;
}
return ans;
}
int inv(int x) {
return ksm(x,P-2);
}
void solve()
{
int n,m;
scanf("%d%d",&n,&m);
printf("%lld\n",1ll*(ksm(2,n-1)-1)*inv(ksm(2,n-1))%P*m%P);
}
int main()
{
int t;
scanf("%d",&t);
while (t--) solve();
}J 小朋友做游戏
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define fs first
#define sc second
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
int T,A,B,n;
int va[10010],vb[10010];
bool cmp(int xx,int yy){
return xx>yy;
}
int suma[10010],sumb[10010];
int main(){
cin>>T;
while(T--){
cin>>A>>B>>n;
rep(i,1,A) scanf("%d",&va[i]);
rep(i,1,B) scanf("%d",&vb[i]);
int mxb=min(n/2,B);
if(A+mxb<n){
puts("-1");
continue;
}
sort(va+1,va+1+A,cmp);
sort(vb+1,vb+1+B,cmp);
rep(i,1,A) suma[i]=suma[i-1]+va[i];
rep(i,1,B) sumb[i]=sumb[i-1]+vb[i];
int ans=-1;
rep(ia,0,A){
int ib=n-ia;
if(ib>mxb||ib<0) continue;
ans=max(ans,suma[ia]+sumb[ib]);
}
assert(ans!=-1);
printf("%d\n",ans);
}
return 0;
}
K 冒险公社
简约美版本：
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define fs first
#define sc second
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
int n;
// 0G 1B 2R
int dp[100010][27];
const int inf=-1e6;
char s[100010];
int cnt(int x){
int g=(x%3==0)+(x/3%3==0)+(x/9%3==0);
int r=(x%3==2)+(x/3%3==2)+(x/9%3==2);
return g-r;
}
int main(){
scanf("%d%s",&n,s+1);
rep(i,0,n+5){
rep(j,0,26) dp[i][j]=inf;
}
rep(j,0,26){
if(s[3]=='G'&&cnt(j)<=0) continue;
if(s[3]=='B'&&cnt(j)!=0) continue;
if(s[3]=='R'&&cnt(j)>=0) continue;
dp[3][j]=(j%3==0)+(j/3%3==0)+(j/9%3==0);
}
rep(i,4,n){
rep(j,0,26){
if(s[i]=='G'&&cnt(j)<=0) continue;
if(s[i]=='B'&&cnt(j)!=0) continue;
if(s[i]=='R'&&cnt(j)>=0) continue;
rep(k,0,26){
if(k%3==j/3%3&&k/3%3==j/9%3){
dp[i][j]=max(dp[i][j],dp[i-1][k]+(j%3==0));
}
}
}
}
int ans=inf;
rep(j,0,26) ans=max(ans,dp[n][j]);
if(ans<0) puts("-1");
else printf("%d\n",ans);
return 0;
}暴力美学版本：
#include<iostream>
#include<string.h>
using namespace std;
int f[100010][4][4][4];//在i前三个为j k p的绿色个数
int main()
{
int n;
string s;
cin>>n;
cin>>s;
s=" "+s;
// hei hong lv
memset(f,-1,sizeof f);
if(s[n]=='G')
{
f[n][1][1][1]=3;
f[n][1][1][3]=2;
f[n][1][3][1]=2;
f[n][3][1][1]=2;
f[n][1][1][2]=2;
f[n][1][2][1]=2;
f[n][2][1][1]=2;
f[n][1][3][3]=1;
f[n][3][1][3]=1;
f[n][3][3][1]=1;
}
if(s[n]=='R')
{
f[n][2][2][2]=0;
f[n][2][2][3]=0;
f[n][2][3][2]=0;
f[n][3][2][2]=0;
f[n][2][2][1]=1;
f[n][2][1][2]=1;
f[n][1][2][2]=1;
f[n][2][3][3]=0;
f[n][3][2][3]=0;
f[n][3][3][2]=0;
}
if(s[n]=='B')
{
f[n][3][3][3]=0;
f[n][3][1][2]=1;
f[n][3][2][1]=1;
f[n][1][3][2]=1;
f[n][2][3][1]=1;
f[n][2][1][3]=1;
f[n][1][2][3]=1;
}
for(int i=n-1;i>=3;i--)
{
if(s[i]=='G')
{
for(int j=1;j<=3;j++)
{
if(f[i+1][1][1][j]!=-1)f[i][1][1][1]=max(f[i][1][1][1],f[i+1][1][1][j]+1);
if(f[i+1][1][3][j]!=-1)f[i][1][1][3]=max(f[i][1][1][3],f[i+1][1][3][j]+1);
if(f[i+1][3][1][j]!=-1)f[i][1][3][1]=max(f[i][1][3][1],f[i+1][3][1][j]+1);
if(f[i+1][1][1][j]!=-1)f[i][3][1][1]=max(f[i][3][1][1],f[i+1][1][1][j]);
if(f[i+1][1][2][j]!=-1)f[i][1][1][2]=max(f[i][1][1][2],f[i+1][1][2][j]+1);
if(f[i+1][2][1][j]!=-1)f[i][1][2][1]=max(f[i][1][2][1],f[i+1][2][1][j]+1);
if(f[i+1][1][1][j]!=-1)f[i][2][1][1]=max(f[i][2][1][1],f[i+1][1][1][j]);
if(f[i+1][3][3][j]!=-1)f[i][1][3][3]=max(f[i][1][3][3],f[i+1][3][3][j]+1);
if(f[i+1][1][3][j]!=-1)f[i][3][1][3]=max(f[i][3][1][3],f[i+1][1][3][j]);
if(f[i+1][3][1][j]!=-1)f[i][3][3][1]=max(f[i][3][3][1],f[i+1][3][1][j]);
}
}
if(s[i]=='R')
{
for(int j=1;j<=3;j++)
{
if(f[i+1][2][2][j]!=-1)f[i][2][2][2]=max(f[i][2][2][2],f[i+1][2][2][j]+0);
if(f[i+1][2][3][j]!=-1)f[i][2][2][3]=max(f[i][2][2][3],f[i+1][2][3][j]+0);
if(f[i+1][3][2][j]!=-1)f[i][2][3][2]=max(f[i][2][3][2],f[i+1][3][2][j]+0);
if(f[i+1][2][2][j]!=-1)f[i][3][2][2]=max(f[i][3][2][2],f[i+1][2][2][j]+0);
if(f[i+1][2][1][j]!=-1)f[i][2][2][1]=max(f[i][2][2][1],f[i+1][2][1][j]);
if(f[i+1][1][2][j]!=-1)f[i][2][1][2]=max(f[i][2][1][2],f[i+1][1][2][j]);
if(f[i+1][2][2][j]!=-1)f[i][1][2][2]=max(f[i][1][2][2],f[i+1][2][2][j]+1);
if(f[i+1][3][3][j]!=-1)f[i][2][3][3]=max(f[i][2][3][3],f[i+1][3][3][j]+0);
if(f[i+1][2][3][j]!=-1)f[i][3][2][3]=max(f[i][3][2][3],f[i+1][2][3][j]+0);
if(f[i+1][3][2][j]!=-1)f[i][3][3][2]=max(f[i][3][3][2],f[i+1][3][2][j]+0);
}
}
if(s[i]=='B')
{
for(int j=1;j<=3;j++)
{
if(f[i+1][3][3][j]!=-1)f[i][3][3][3]=max(f[i][3][3][3],f[i+1][3][3][j]);
if(f[i+1][1][2][j]!=-1)f[i][3][1][2]=max(f[i][3][1][2],f[i+1][1][2][j]);
if(f[i+1][2][1][j]!=-1)f[i][3][2][1]=max(f[i][3][2][1],f[i+1][2][1][j]);
if(f[i+1][3][2][j]!=-1)f[i][1][3][2]=max(f[i][1][3][2],f[i+1][3][2][j]+1);
if(f[i+1][3][1][j]!=-1)f[i][2][3][1]=max(f[i][2][3][1],f[i+1][3][1][j]);
if(f[i+1][1][3][j]!=-1)f[i][2][1][3]=max(f[i][2][1][3],f[i+1][1][3][j]);
if(f[i+1][2][3][j]!=-1)f[i][1][2][3]=max(f[i][1][2][3],f[i+1][2][3][j]+1);
}
}
}
int ans=-1;
for(int i=0;i<=3;i++)
for(int j=0;j<=3;j++)
for(int p=0;p<=3;p++)
ans=max(ans,f[3][i][j][p]);
cout<<ans<<endl;
}L 牛牛学走路
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define fs first
#define sc second
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
int T,n;
char s[1010];
int main(){
cin>>T;
while(T--){
scanf("%d%s",&n,s+1);
int x=0,y=0;
db ans=0;
rep(i,1,n){
if(s[i]=='U') y++;
if(s[i]=='D') y--;
if(s[i]=='L') x--;
if(s[i]=='R') x++;
ans=max(ans,hypot(x,y));
}
printf("%.12lf\n",ans);
}
return 0;
}
