2022济南大学acm新生赛题解

通过答题情况的难度系数：

签到：ABL

简单：DGKQ

中等：CMN

困难：EFHIJOPRST

A-和

算出n个数的和判断正负性即可！！！

发现很多同学的代码错误：要么sum未赋初值，要么数组大小定义太小导致数组溢出！！！

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define endl '\n'
#define close ios::sync_with_stdio(false),cin.tie(0)
using namespace std;
const int N=2e5+5;
 
void solve(){
    int n;
    cin>>n;
    int sum=0;
    while(n--){
        int x;
        cin>>x;
        sum+=x;
    }
    if(sum==0) cout<<"zero"<<endl;
    else if(sum>0) cout<<"positive"<<endl;
    else cout<<"negative"<<endl;
}
 
int main()
{
    close;
    int _=1;
    while(_--){
        solve();
    }
    return 0;
}

B-积

直接计算n个数的积的话，结果会导致爆long long，判断积的正负性只需找到负数的个数，如果出现了0，结果即0；否则如果出现负数的个数为偶数个，结果即为正数，否则即为负数！！

发现很多同学们的代码都直接算出n个数的积，结果会导致爆long long和int，故不能直接乘！

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,s=1,x;
    cin>>n;
    while(n--){
        scanf("%d",&x);
        if(x<0) s*=-1;
        if(!x) s*=0;
    }
    puts(s>0?"positive":s?"negative":"zero");
}

C-马

直接DFS或者BFS即可！！！

本来打算放这个基础搜索题目做个简单题，但是发现很多同学不会搜索，导致题目N过的人数也很少！！！

BFS做法：

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define endl '\n'
#define close ios::sync_with_stdio(false),cin.tie(0)
using namespace std;
const int N=2e5+5;
int vis[55][55][55];
struct node{
    int x,y,z;
};
 
void solve(){
    int n,m,h,t,stx,sty,stz;
    cin>>n>>m>>h>>stx>>sty>>stz>>t;
    vector<node>d(t);
    for(int i=0;i<t;i++){
        cin>>d[i].x>>d[i].y>>d[i].z;
    }
    queue<node>q;
    q.push({stx,sty,stz});
    int ans=0;
    while(!q.empty()){
        node u=q.front();
        q.pop();
        if(vis[u.x][u.y][u.z]) continue;
        //cout<<u.x<<" "<<u.y<<" "<<u.z<<endl;
        vis[u.x][u.y][u.z]=1;
        ans++;
        for(int i=0;i<t;i++){
            int tx=u.x+d[i].x,ty=u.y+d[i].y,tz=u.z+d[i].z;
            if((tx>=1&&tx<=n)&&(ty>=1&&ty<=m)&&(tz>=1&&tz<=h)){
                if(vis[tx][ty][tz]) continue;
                q.push({tx,ty,tz});
            }
        }
    }
    cout<<ans<<endl;
}
 
int main()
{
    close;
    int _=1;
    //cin>>_;
    while(_--){
        solve();
    }
    return 0;
}

DFS做法：

#include<bits/stdc++.h>
using namespace std;
int a[31][3],ans,t,n,m,h;
bool f[51][51][51];
void dfs(int x,int y,int z){
    f[x][y][z]=1,ans++;
    for(int i=1;i<=t;i++){
        int X=x+a[i][0],Y=y+a[i][1],Z=z+a[i][2];
        if(X>0&&X<=n&&Y>0&&Z>0&&Y<=m&&Z<=h&&!f[X][Y][Z]) dfs(X,Y,Z);
    }
}
int main(){
    int x,y,z;
    cin>>n>>m>>h>>x>>y>>z>>t;
    for(int i=1;i<=t;i++) cin>>a[i][0]>>a[i][1]>>a[i][2];
    dfs(x,y,z),cout<<ans;
}

D-数 

由题意可知，当n或m足够大的时候，总有一个值在[1,10]这个区间上，故可直接枚举大小更小的那个 集合作为二元有序对其中的一个数。例如：当集合A中的3时，集合B的大小为m(m>3)，要满足此二元有序对，取集合m中大于3的数有m/3-1个，小于等于3的数可直接循环枚举！！！

发现一开始大部分同学都是直接O(n*m)暴力，学校oj判题都是直接把整个程序跑完，才判出TLE，导致oj直接爆了！！！一般的oj，1s钟可以跑4e8次左右，做题之前需先算出时间复杂度合不合适，再考虑实现代码！！！

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define endl '\n'
#define close ios::sync_with_stdio(false),cin.tie(0)
using namespace std;
const int N=2e5+5;
 
void solve(){
    ll n,m;
    cin>>n>>m;
    if(n>m) swap(n,m);
    ll ans=0;
    for(int i=1;i<=n;i++){
        ans+=m/i-1;
        for(int j=1;j<=i;j++){
            if(i%j==0) ans++;
        }
    }
    cout<<ans<<endl;
}
 
int main()
{
    close;
    int _=1;
    while(_--){
        solve();
    }
    return 0;
}

E-X限祖玛

在轮到玩家进行操作的时候，肯定是只要能选上连续X个相同颜色的祖玛球最优，故之间判断整个序列能操作的最大数max，max偶数即后者赢，否则前者赢！

#include <bits/stdc++.h>
 
using namespace std;
const int N = 1e5 + 10;
char a[N];
 
int main() {
    int n, x;
    scanf("%d%d", &n, &x);
    scanf("%s", a + 1);
    pair<char, int> stk[N];
    int top = 0;
    int cnt = 0;
    for (int i = 1; i <= n; ) {
        int j = i;
        while (j <= n && a[i] == a[j]) j ++;
        // [i, j - 1]
        int stklen = 0;
        if (top && stk[top].first == a[i])
            stklen = stk[top].second; 
        int len = j - i + stklen;
        cnt += len / x;
        stk[++top] = {a[i], len - len / x * x};
         
        if (top && stk[top].first == a[i]) {
            while (top && stk[top].first == a[i]) top --;
        }
        if (len % x != 0)
            stk[++top] = {a[i], len % x}; 
        i = j;
    }
    if (cnt & 1)
        puts("Fang is winner");
    else
        puts("Liang is winner");    
}

F-合成大魔棒

可发现所有树枝的价值小于等于1e9，故合并的次数最大是1000次，大于1000次，最后合成得到的值为负数，故不必考虑合成次数大于1000次的情况；

在考虑x次合并的时候，肯定是连续x+1合并得到的最大值最优，比如：1，2，3，4，5；此时合并两次，肯定是将后面连续3个数合并得到最大值12，如果2和3合并，4和5合并，此时最大值9，故无法保证此合并方案最优！

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int Max=1e6+5;
int a[Max];
int pre[Max];
int ans=0;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        // scanf("%d",&a[i]);
        pre[i]=pre[i-1]+a[i];
    }
    int maxa=0;
    for(int i=1;i<=min(1000,n);i++){
        for(int j=1;j<=n;j++){
            int r=j+i-1;
            if(r>n) break;
            maxa=max(maxa,pre[r]-pre[j-1]-(i-1)*(i-1)*(i-1));
        }
    }
    cout<<maxa<<endl;
}

G-高铁路线规划

结论题：不能有三元环 那图必定是满二分图，所以题目变成求x+y=n 且xy最大，xy=x*(n-x)，明显一个二次函数，取x=n/2的时候，x*(n-x)最大！！

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    while(scanf("%d",&n)&&~n) printf("%d\n",n/2*(n-n/2));
}

H-咕咕酱的饼

方法一：简单思维题，定义总面积为ans，如果向右移动，则加上此时向右移动增加的线段、线段两端向坐标轴做垂线与x轴组成的面积，如果向左移动，则减去此时向左移动增加的线段、线段两端向坐标轴做垂线与x轴组成的面积，向上，向下移动，更新此时的纵坐标y！

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
    int n,x=0,y=0,z;
    ll ans=0;
    char s[1];
    cin>>n;
    while(n--){
        scanf("%s%d",s,&z);
        if(s[0]=='W') y+=z;
        if(s[0]=='S') y-=z;
        if(s[0]=='A') x-=z,ans-=1ll*z*y;
        if(s[0]=='D') x+=z,ans+=1ll*z*y;
    }
    cout<<abs(ans);
}

方法二：直接求多边形面积也行，可参考这篇博客了解多边形面积的求法：多边形面积计算_计算多边形面积_GISVertex的博客-CSDN博客

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int Max=1e6+5;
struct node{
    ll x,y;
};
node W[100];
int w=0,a=0,s=0,d=0;
int main(){
    int n;
    cin>>n;
    ll x=0,y=0;
    double ans=0;
    W[0]={0,0};
    for(int i=1;i<=n;i++){
        char ch;ll num;
        cin>>ch>>num;
        ll nx,ny;
        if(ch=='W'){//上
            nx=x;ny=y+num;
            W[++w]={nx,ny};
        }else if(ch=='S'){//下
            nx=x;ny=y-num;
            W[++w]={nx,ny};
        }else if(ch=='A'){//左
            nx=x-num;ny=y;
            W[++w]={nx,ny};
        }else{//右
            nx=x+num;ny=y;
            W[++w]={nx,ny};
        }
        x=nx;y=ny;
    }
    for(int i=0;i<w;i++){
        ans+=0.5*(W[i].x*W[i+1].y-W[i].y*W[i+1].x);
    }
    ans=fabs(ans);
    printf("%.0lf\n",ans);
}

I-咕咕酱的密码锁

简单思维题，其中存在某一行或者某一列的按钮不被按下，故这一行（一列）的增加的数字只能是列（行）的按钮所增加的，故根据给出未按下的行（列）就可以直到列（行）增加的次数，剩下的数即是行（列）增加的次数！！

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int Max=1e6+5;
int a[Max],b[Max];
int room[105][105];
int main(){
    int n,m;
    cin>>n>>m;
    char ch;int p;
    cin>>ch>>p;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>room[i][j];
        }
    }
    if(ch=='R'){
        for(int i=1;i<=m;i++){
            a[i]=room[p][i];
            for(int j=1;j<=n;j++){
                room[j][i]-=a[i];
            }
        }
        for(int i=1;i<=n;i++) b[i]=room[i][1];
    }else{
        for(int i=1;i<=n;i++){
            b[i]=room[i][p];
            for(int j=1;j<=m;j++){
                room[i][j]-=b[i];
            }
        }
        for(int i=1;i<=m;i++) a[i]=room[1][i];
    }
    for(int i=1;i<=n;i++) cout<<b[i]<<' ';puts("");
    for(int i=1;i<=m;i++) cout<<a[i]<<' ';puts("");
     
}

J-生徒会主席的竞选

背包dp，定义dp[i][j]为前i个人有效票产生j张的最小原始票数，转移方程：


dp[i][j]=min(dp[i-1][j-a[i]]+a[i]/2+1,dp[i][j]);
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int Max=1e6+5;
int a[Max];
int dp[1005][1005];
int main(){
    int n;
    cin>>n;int sum=0;
    for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];
    for(int i=0;i<=1000;i++){
        for(int j=0;j<=1000;j++) dp[i][j]=1e9;
    }
    for(int i=0;i<=n;i++)
    dp[i][0]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=1000;j++){
            dp[i][j]=dp[i-1][j];
            if(j-a[i]>=0) dp[i][j]=min(dp[i-1][j-a[i]]+a[i]/2+1,dp[i][j]);
            // cout<<i<<' '<<j<<' '<<dp[i][j]<<endl;
        }
    }
    int mina=1e9;
    for(int i=sum/2+1;i<=1000;i++){
        mina=min(mina,dp[n][i]);
    }
    cout<<mina<<endl;
}

K-Syan的最大值

        容易知道将全部数字进行或操作最优！

这题过的人数很少，出乎我们意料，可能大部分同学没有接触过位运算，学过计组之后可能会更清楚一些，但是后面我们加上了样例解释，还是很多同学不敢做，其实第一位同学提交的代码思路完全正确，只是数组开太小导致溢出，不知为何放弃做这题了 ！一般看到评测结果运行错误，大概率原因就是数组开小导致溢出！

#include <bits/stdc++.h>

using namespace std;

const int N=1e5+5;
int a[N];
int main() {
	int n;cin>>n;
	int ans=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		ans|=a[i];
	}
	cout<<ans<<endl;
}

L-Syan的无限循环小数（easy）

        如题意可知，给出的a,b都在[1,5]这个区间，可直接手动枚举知道1/3，2/3，4/3，5/3是无线循环小数！ 

#include <bits/stdc++.h>

using namespace std;

int main() {
    int a,b;
    cin>>a>>b;
    if(a==1&&b==3) printf("YES\n");
    else if(a==2&&b==3) printf("YES\n");
    else if(a==4&&b==3) printf("YES\n");
    else if(a==5&&b==3) printf("YES\n");
    else printf("NO\n");
}

M-Syan的无限循环小数（hard）

        这题不同于L，给出的a,b都在[1,1000000000]这个区间，不可直接手动枚举，这时就需要知道这结论：将分数化为最简分数后，分母的全部因数（除去1和其自身）没有为2或5以外的数，则该分数就不是无限循环小数；否则为无限循环小数。

#include <bits/stdc++.h>

using namespace std;

int main() {
	int a, b;
	cin >> a >> b;
	int g = __gcd(a, b);
	a /= g, b /= g;
	if (a % b == 0)
		puts("NO");
	else {
		while (b % 2 == 0)
			b /= 2;
		while (b % 5 == 0)
			b /= 5;
		puts(b == 1 ? "NO" : "YES");
	}
}

N-Syan的最大金币数

        由题意可知，玩家可以从起点无数次到达终点，直到迷宫中可取的金币全部获得。从起点到达一个方格，如若想到获得迷宫中的金币，就必须再从此处到达终点，走出迷宫，例如样例

f206f5215d6f4a8d8e5c9a4dba1a9302.png

 当走到（3，1）处时，此时只能往（4，1）和（3，2）走，但是（3，2）有障碍不能到达，走到（4，1）也是死路，故（3，1）处的金币无法获得！！！

故只需判断从起点（1，1）往终点（n，m）走，从终点（n，m）往起点（1，1）走，如果这两个方向都能到达一个方格，则此时的金币即可获得，做两次BFS即可！！！

#include <bits/stdc++.h>
using namespace std;
#define sc(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ll long long
#define pb push_back
const int Max=1e6+5;
const int Mod=998244353;
const int mod=998244353;
bool vis[1005][1005];
struct node{
    int x,y;
};
int dir[2][2]={1,0,0,1};
bool flag[1005][1005];
int n;int m;
bool check(int x,int y){
    if(x>=1&&x<=n&&y>=1&&y<=n) return true;
    return false;
}
void bfs(int start_x,int start_y){
    node start,next;
    queue<node>q;
    q.push({start_x,start_y});
    flag[start_x][start_y]=true;
    while(!q.empty()){
        start=q.front();
        q.pop();
        for(int i=0;i<2;i++){
            next.x=start.x+dir[i][0];
            next.y=start.y+dir[i][1];
            
            if(check(next.x,next.y)&&!vis[next.x][next.y]&&!flag[next.x][next.y]){
                q.push(next);
                flag[next.x][next.y]=true;
            }
        }
    }
}
bool flag1[1005][1005];
int dir1[2][2]={-1,0,0,-1};
void bfs1(int start_x,int start_y){
    node start,next;
    queue<node>q;
    q.push({start_x,start_y});
    flag1[start_x][start_y]=true;
    while(!q.empty()){
        start=q.front();
        q.pop();
        for(int i=0;i<2;i++){
            next.x=start.x+dir1[i][0];
            next.y=start.y+dir1[i][1];
            if(check(next.x,next.y)&&!vis[next.x][next.y]&&!flag1[next.x][next.y]){
                q.push(next);
                flag1[next.x][next.y]=true;
            }
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        vis[x][y]=true;
    }
    bfs(1,1);
    bfs1(n,n);
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==1&&j==1) continue;
            if(flag[i][j]&&flag1[i][j]) ans++;
        }
    }
    cout<<ans<<endl;
}

O-Syan的三元组

这题提交的人也有很多直接O(n*n*n)直接暴力，没有实现算明白时间复杂度！！！

方法一： 由D=|a-b|+|b-c|+|a-c|可知，当a=b=c的时候，距离最小，其余情况：

6792841f2ca24f71b69bce9aa564f23a.png

 可知

L1=|a-b|；   L1=|b-c|；   L3=|a-c|；

D=|a-b|+|b-c|+|a-c|=L1+L2+L3=2L3；

由D的表达式可知，事实上决定D大小的关键时a和c的距离，于是问题就可以简化为每次固定c找一个a，使得L3=|c-a|最小；

#include <bits/stdc++.h>

using namespace std;

const int N=1e5+5;
int a[N],b[N],c[N];

int main() {
	int n;cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		cin>>b[i];
	}
	for(int i=1;i<=n;i++){
		cin>>c[i];
	}
	sort(a+1,a+1+n);
	sort(b+1,b+1+n);
	sort(c+1,c+1+n);
	int i=1,j=1,k=1;
	long long ans=1e18;
	while(i<=n&&j<=n&&k<=n){
		long long D=abs(a[i]-b[j])+abs(b[j]-c[k])+abs(a[i]-c[k]);
		ans=min(ans,D);
		if(a[i]<=b[j]&&a[i]<=c[k]) i++;
		else if(b[j]<=a[i]&&b[j]<=c[k]) j++;
		else k++;
	}
	printf("%lld\n",ans);
}

方法二：也可以固定中间b的值，然后在a，c数组中二分找到距离b最近的一个值！！！

（附上王逸鸣学长的代码）

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define endl '\n'
#define close ios::sync_with_stdio(false),cin.tie(0)
using namespace std;
const int N=2e5+5;
 
void solve(){
    int n;
    cin>>n;
    set<ll>s1,s2,s3;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        s1.insert(x);
    }
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        s2.insert(x);
    }
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        s3.insert(x);
    }
    ll ans=3e10;
    for(auto i:s1){
        auto j=s2.lower_bound(i),k=s3.lower_bound(i);
        if(j==s2.end()||k==s3.end()) continue;
        ans=min(ans,abs(i-*j)+abs(i-*k)+abs(*j-*k));
    }
    for(auto j:s2){
        auto i=s1.lower_bound(j),k=s3.lower_bound(j);
        if(i==s1.end()||k==s3.end()) continue;
        ans=min(ans,abs(*i-j)+abs(*i-*k)+abs(j-*k));
    }
    for(auto k:s3){
        auto j=s2.lower_bound(k),i=s1.lower_bound(k);
        if(j==s2.end()||i==s1.end()) continue;
        ans=min(ans,abs(*i-*j)+abs(*i-k)+abs(*j-k));
    }
    cout<<ans<<endl;
}
 
int main()
{
    close;
    int _=1;
    while(_--){
        solve();
    }
    return 0;
}

P-Shiki的二元组

二分找第k个小的数，check判断二分此时的mid前面有几个比其小的数！

这题新生做之前可能还有很多同学没有接触二分！

#include <bits/stdc++.h>
using namespace std;
#define sc(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ll long long
#define pb push_back
const int Max=1e6+5;
const int Mod=998244353;
ll a[Max],b[Max];
int main(){
    int n;sc(n);
    ll k;sl(k);
    for(int i=1;i<=n;i++) sl(a[i]);
    for(int i=1;i<=n;i++) sl(b[i]);
    sort(a+1,a+1+n);
    sort(b+1,b+1+n);
    ll l=0,r=1e18;
    ll x=0;
    while(l<=r){
        ll mid=(l+r)/2;
        ll ans=0;
        bool flag=false;ll sum;
        for(int i=1;i<=n;i++){
            // if(flag) break;
            if(a[i]*b[n]<=mid) ans+=n;
            else{
                int L=1,R=n;
                while(L<=R){
                    int Mid=(L+R)/2;
                    if(a[i]*b[Mid]>mid) R=Mid-1;
                    else L=Mid+1;
                }
                // cout<<mid<<' '<<L<<' '<<R<<endl;
                ans+=R;
            }
        }
        if(ans<k) l=mid+1;
        else r=mid-1;
    }
    printf("%lld\n",l);
}

Q-被守护者的灵柩

直接判断t是否是s的子序列，时间复杂度O(n*n)。循环t字符串，找到t[1]第一次出现在s的位置，然后依次找t[i]（在t[i-1]出现在s的位置之后出现t[i]的第一个位置，i>1）.

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int Max=1e6+5;
char a[Max],b[Max];
int main(){
    scanf("%s",a+1);
    scanf("%s",b+1);
    int len=strlen(b+1);
    int len_a=strlen(a+1);
    int j=1;
    bool flag=true;
    for(int i=1;i<=len;i++){
        while(j<=len_a&&b[i]!=a[j]){
            j++;
        }
        if(b[i]==a[j]) j++;
        else{
            flag=false;break;
        }
    }
    if(flag) printf("yes\n");
    else printf("no\n");
}

R-千手百眼 天下人间

本题考查裴蜀定理：若a，b是整数，且gcd(a,b)=d，那么对于任意的整数x，y，ax+by都一定是d的倍数，特别的，一定存在整数x，y，使得ax+by=d成立。

具体证明可参考这篇博客：裴蜀定理_Hypoc_的博客-CSDN博客

故这题只需计算n个数的gcd，然后判断这是否是m的因子即可！

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int Max=1e6+5;
int a[Max],b[Max];
map<int,bool>mp;
int main(){
    int n;cin>>n;int m;cin>>m;m=abs(m);
    cin>>a[1];
    int num=a[1];
    for(int i=2;i<=n;i++){
        cin>>a[i];
        num=__gcd(num,a[i]);
    }
    if(m%num==0) printf("yes\n");
    else printf("no\n");
}

S-流转存续的花神诞祭（dp）

方法一：定义状态dp[i]表示到达梦境i的方案数，pre_a[i]表示前i个梦境的推理难度和，pre_b[i]表示前i个梦境的梦境深度和，梦境i能到达的i+1~i+k，状态转移方程为

dp[i+1~i+k]+=dp[i]

很显然，这就变成了单点询问+区间修改问题，利用树状数组维护即可！

每个梦境i能到达的最大梦境i+k可以前缀和+二分求得k

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int Max=1e6+5;
const ll INF=1e15+5;
const ll mod=998244353;
ll n,x,y;
int lowbit(int x){
    return x&-x;
}
long long tree[Max];
void update(int x,ll y){
    while(x<=n){
        tree[x]+=y;
        x+=lowbit(x);
    }
}
long long getsum(int x){
    long long sum=0;
    while(x){
        sum+=tree[x];
        x-=lowbit(x);
    }
    return sum%mod;
}
ll pre_a[Max],pre_b[Max];
ll a[Max],b[Max];
int main(){
    scanf("%lld%lld%lld",&n,&x,&y);
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&a[i],&b[i]);
        pre_a[i]=pre_a[i-1]+a[i];
        pre_b[i]=pre_b[i-1]+b[i];
    }
    for(int i=0;i<=n;i++){
        int l=i+1,r=n,X=-1;
        while(l<=r){
            int mid=(l+r)/2;
            if(pre_a[mid]-pre_a[i]>x||pre_b[mid]-pre_b[i]>y) r=mid-1;
            else{
                X=mid,l=mid+1;
            }
        }
        if(X==-1) continue;
        ll ans=1;
        if(i) ans=getsum(i);
        update(i+1,ans);
        update(r+1,-ans);
    }
    printf("%lld\n",getsum(n));
}

方法二：前缀和+dp

        定义状态f[i]表示到达前i个梦境的方案数，问题转化为第i个梦境可能由第i-k~i-1个梦境转移过来，第i个梦境可能是[i-k,i-1]转移过来，那么第i+1个梦境最大区间范围只可能是在第i个梦境区间[i-k,i-1]的基础上加上第i个，这样就是[i-k,i]，如果不满足推理难度<=x和梦境深度<=y，一个一个删除区间最左边的值，直到符合推理难度<=x和梦境深度<=y，第i+2个梦境在第i+1个梦境的基础以此类推得到转移方程

f[i]=((s?f[i-1]-f[s-1]:f[i-1])+1ll*f[i-1])%mod;
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5,mod=998244353;
long long a[N],b[N],f[N];
int main(){
    int n,X,Y,s=0,s1=0,s2=0;
    scanf("%d%d%d",&n,&X,&Y),f[0]=1;
    for(int i=1;i<=n;i++) scanf("%lld%lld",&a[i],&b[i]);
    for(int i=1;i<=n;i++){
        s1+=a[i],s2+=b[i];
        while(s1>X||s2>Y) s++,s1-=a[s],s2-=b[s];
        f[i]=((s?f[i-1]-f[s-1]:f[i-1])+1ll*f[i-1])%mod;
    }
    printf("%d\n",(1ll*f[n]-f[n-1]+mod)%mod);
}

T-命运尽头的垂泪者

模拟题，按照题意模拟即可！

#include <bits/stdc++.h>
using namespace std;
#define sc(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ll long long
#define pb push_back
const double esp=1e-8;
const int Max=1e6+5;
const int Mod=998244353;
ll a[Max],b[Max];
queue<int>q;
int main(){
    int n;
    double h,m,k;
    cin>>n>>h>>m>>k;
    double M=m,H=h;
    double st_cao=0;double cao=0;
    for(int i=1;i<=n;i++){
        cao-=st_cao;
        string str;
        double cnt,dmg;
        cin>>str;
        if(str=="Physico") cin>>dmg;
        else cin>>cnt>>dmg;
        if(str=="Anemo"){//风
            m-=0.5*cnt;
            m-=0.2*M*dmg/H;
        }else if(str=="Geo"){//岩
            m-=0.5*cnt;
            m-=0.2*M*dmg/H;
        }else if(str=="Electro"||str=="Pyro"){//雷火
            if(str=="Pyro") m-=2*cnt;
            else m-=cnt;
            m-=0.2*M*dmg/H;
            int len=q.size();
            len=min(len,2);
            m-=0.2*6*k*len*M/H;
            while(!q.empty()) q.pop();
        }else if(str=="Dendro"){//草
            m-=0.2*M*dmg/H;
            if(cao>esp){
                cao=max(cao,0.8*cnt);
            }else{
                cao=0.8*cnt;
                st_cao=1.6*cnt/(14+5*cnt);
            }
              
        }else if(str=="Hydro"){//水
            m-=0.2*M*dmg/H;
            if(cao>esp){
                cao-=0.5*cnt;
                q.push(i);
            } 
        }else if(str=="Cryo"){//冰
              
        }else if(str=="Physico"){//物理
            m-=0.2*M*dmg/H;
        }
    }
    while(!q.empty()){
          
        if(n-q.front()==6){
            m-=0.2*M*4*k/H;;
            // h-=4*k;
        }q.pop();
    }
    double sum=m*100.0/M;
    if(sum>esp) printf("%.2lf%%\n",sum);
    else printf("win\n");
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/145.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

DDOS攻击

DDOS攻击

注&#xff1a;本博客只是为了自己的学习&#xff0c;记录自己的学习&#xff0c;请勿用于其他途径、1、winR-->cmd2、ping 网站3、替换IP1 import java.io.BufferedInputStream;2 import java.io.IOException;3 import java.net.MalformedURLException;4 import java.net.U…
阅读更多...
Vue3做出B站【bilibili】 Vue3+TypeScript+ant-design-vue【快速入门一篇文章精通系列（一）前端项目案例】

Vue3做出B站【bilibili】 Vue3+TypeScript+ant-design-vue【快速入门一篇文章精通系列（一）前端项目案例】

本项目分为二部分 1、后台管理系统&#xff08;用户管理&#xff0c;角色管理&#xff0c;视频管理等&#xff09; 2、客户端&#xff08;登录注册、发布视频&#xff09; Vue3做出B站【bilibili】 Vue3TypeScriptant-design-vue【快速入门一篇文章精通系列&#xff08;一&…
阅读更多...
【C++】STL简介 及 string的使用

【C++】STL简介 及 string的使用

文章目录1. STL简介1.1 什么是STL1.2 STL的版本1.3 STL的六大组件2. string类的使用2.1 C语言中的字符串2.2 标准库中的string类2.3 string类的常用接口说明1. string类对象的常见构造2. string类对象的容量操作3. string类对象的修改操作4. resize和reserve5. 认识迭代器&…
阅读更多...
产品研发项目进度管理软件工具有哪些推荐？整理10款最佳进度管理软件

产品研发项目进度管理软件工具有哪些推荐？整理10款最佳进度管理软件

项目进度管理是确保项目按时完成的关键过程&#xff0c;使用合适的项目进度管理工具能确保帮助项目管理者实时了解和控制项目的进展情况&#xff0c;及时发现和解决问题&#xff0c;减少项目风险&#xff0c;提高项目效率和管理水平。这里将整理出国内外最受欢迎的10款项目进度…
阅读更多...
ASEMI低压MOS管SI2301参数，SI2301体积，SI2301尺寸

ASEMI低压MOS管SI2301参数，SI2301体积，SI2301尺寸

编辑-Z ASEMI低压MOS管SI2301参数&#xff1a; 型号&#xff1a;SI2301 漏极-源极电压&#xff08;VDS&#xff09;&#xff1a;20V 栅源电压&#xff08;VGS&#xff09;&#xff1a;8V 漏极电流&#xff08;ID&#xff09;&#xff1a;2.3A 功耗&#xff08;PD&#xf…
阅读更多...
Simulink壁咚(一)——What and How

Simulink壁咚(一)——What and How

目录 一、前言 二、Simulink 知多少 三、滤波算法 四、Model Verification 五、Model Coverage 六、Simulink测试实例 七、Simulink Test 八、Test Manager 九、Test Harness 十、 学习 一、前言 Simulink从2017b以后更加工程化和实用化&#xff0c;基于MBD的功能日趋…
阅读更多...
MATLAB绘制ROC曲线

MATLAB绘制ROC曲线

ROC曲线(Receiver Operating Characteristic Curve) 1 简介 ROC曲线是用于评估二元分类模型&#xff08;如Logistic回归&#xff09;表现优劣的一种工具&#xff0c;其横轴表示假阳性率&#xff08;false positive rate&#xff0c;FPR&#xff09;&#xff0c;即实际为负例但…
阅读更多...
MySQL事务详解

MySQL事务详解

&#x1f3c6;今日学习目标&#xff1a; &#x1f340;Spring事务和MySQL事务详解 ✅创作者&#xff1a;林在闪闪发光 ⏰预计时间&#xff1a;30分钟 &#x1f389;个人主页&#xff1a;林在闪闪发光的个人主页 &#x1f341;林在闪闪发光的个人社区&#xff0c;欢迎你的加入: …
阅读更多...
vue3 构建属于自己的组件库dxui

vue3 构建属于自己的组件库dxui

文章目录前言第一步&#xff0c;通过vue-cli搭建vue3框架第二步&#xff0c;构建一个入口&#xff0c;将所有的组件统一管理第三步 修改package.json &#xff0c;对组件进行单独打包第四步输入命令行开始打包第五步&#xff0c;修改package.json文件&#xff0c;为npm 发布做准…
阅读更多...
[ vulnhub靶机通关篇 ] 渗透测试综合靶场 DC-1 通关详解 (附靶机搭建教程)

[ vulnhub靶机通关篇 ] 渗透测试综合靶场 DC-1 通关详解 (附靶机搭建教程)

&#x1f36c; 博主介绍 &#x1f468;‍&#x1f393; 博主介绍&#xff1a;大家好&#xff0c;我是 _PowerShell &#xff0c;很高兴认识大家~ ✨主攻领域&#xff1a;【渗透领域】【数据通信】 【通讯安全】 【web安全】【面试分析】 &#x1f389;点赞➕评论➕收藏 养成习…
阅读更多...
Python 基础教程【1】：Python介绍、变量和数据类型、输入输出、运算符

Python 基础教程【1】：Python介绍、变量和数据类型、输入输出、运算符

本文已收录于专栏&#x1f33b;《Python 基础》文章目录1、Python 介绍2、变量和数据类型2.1 注释的使用2.2 变量以及数据类型2.2.1 什么是变量&#xff1f;2.2.2 怎么给变量起名&#xff1f;2.2.3 变量的类型&#x1f3a8; 整数 int&#x1f3a8; 浮点数&#xff08;小数&…
阅读更多...
教你成为比卡卡西还牛逼的全能忍者，全拷贝与分割函数

教你成为比卡卡西还牛逼的全能忍者，全拷贝与分割函数

如何成为一个集雷切&#xff0c;写轮眼侦查和拷贝与一身的卡卡西&#xff0c;下面教你&#xff01; 目录 第一式——雷切&#xff01; strtok 第二式——写轮眼侦查&#xff01; strerror函数 第三式——写轮眼拷贝&#xff01; memcpy 模拟实现memcpy函数 &#x1f60e;…
阅读更多...
Hadoop集群搭建

Hadoop集群搭建

文章目录一、运行环境配置(所有节点)1、基础配置2、配置Host二、依赖软件安装(101节点)1、安装JDK2、安装Hadoop(root)3、Hadoop目录结构三、本地运行模式&#xff08;官方WordCount&#xff09;1、简介2、本地运行模式&#xff08;官方WordCount&#xff09;四、完全分布式运行…
阅读更多...
多线程的风险 --- 线程安全

多线程的风险 --- 线程安全

✨个人主页&#xff1a;bit me&#x1f447; ✨当前专栏&#xff1a;Java EE初阶&#x1f447; ✨每日一语&#xff1a;低头赶路&#xff0c;敬事如仪&#xff1b;自知自心&#xff0c;其路则明。 目 录&#x1f378;一. 线程不安全&#x1f379;二. 线程不安全的原因&#x1f…
阅读更多...
看完书上的栈不过瘾，为什么不动手试试呢？

看完书上的栈不过瘾，为什么不动手试试呢？

一.栈的基本概念1.栈的定义栈&#xff08;Stack&#xff09;&#xff1a;是只允许在一端进行插入或删除的线性表。首先栈是一种线性表&#xff0c;但限定这种线性表只能在某一端进行插入和删除操作。其中注意几点&#xff1a;栈顶&#xff08;Top&#xff09;&#xff1a;线性表…
阅读更多...
【C语言蓝桥杯每日一题】—— 单词分析

【C语言蓝桥杯每日一题】—— 单词分析

【C语言蓝桥杯每日一题】—— 单词分析&#x1f60e;前言&#x1f64c;单词分析&#x1f64c;总结撒花&#x1f49e;&#x1f60e;博客昵称&#xff1a;博客小梦 &#x1f60a;最喜欢的座右铭&#xff1a;全神贯注的上吧&#xff01;&#xff01;&#xff01; &#x1f60a;作者…
阅读更多...
三天吃透MySQL面试八股文

三天吃透MySQL面试八股文

本文已经收录到Github仓库&#xff0c;该仓库包含计算机基础、Java基础、多线程、JVM、数据库、Redis、Spring、Mybatis、SpringMVC、SpringBoot、分布式、微服务、设计模式、架构、校招社招分享等核心知识点&#xff0c;欢迎star~ Github地址&#xff1a;https://github.com/…
阅读更多...
C 语言编程 — 线程池设计与实现

C 语言编程 — 线程池设计与实现

目录 文章目录目录线程池&#xff08;Thread Pool&#xff09;tiny-threadpool数据结构设计Task / JobTask / Job QueueWorker / ThreadThread Pool ManagerPublic APIsPrivate Functions运行示例线程池&#xff08;Thread Pool&#xff09; 线程池&#xff08;Thread Pool&am…
阅读更多...
Spring Cloud学习笔记【初识微服务基础框架搭建】

Spring Cloud学习笔记【初识微服务基础框架搭建】

文章目录微服务架构介绍架构图核心组件Spring Cloud版本对应基础框架搭建1.建造父工程2.建造子工程user工程建造auth工程建造RestTemplate 实现微服务远程调用RestTemplate 介绍配置RestTemplate测试远程访问总结微服务架构 介绍 微服务架构是一种将应用程序拆分成小型、自治…
阅读更多...
设计模式之工厂模式

设计模式之工厂模式

工厂模式是设计模式中的经典模式&#xff0c;工厂模式又可分为以下三种类型&#xff1a; 简单工厂模式工厂方法模式抽象工厂模式 这三种模式可以理解为同一种编程思想的三个版本&#xff0c;从简单到高级不断升级。本文将着重介绍简单工厂模式。 简单工厂模式 简单工厂模式&…
阅读更多...
最新文章

Copyright @ 2022~2023