【题目记录】——2021 年百度之星·程序设计大赛 - 初赛二

心已赠人 2022-09-04 03:49 159阅读 0赞

### 文章目录 ###

*  1001 签到 数学 模拟
 *  1002 随机题意 思维
 *  1003 魔怔 图论 欧拉回路
 *  1004 净化 数学，思维

题目地址 [2021 年百度之星·程序设计大赛 - 初赛二][2021 _ -]  
题目原地址 [2021 年百度之星·程序设计大赛 - 初赛二][2021 _ - 1]

# 1001 签到 数学 模拟 #

题目地址[1001 签到][1001]  
题意：给a,b ，每次 a,b 会变为a+b,a−b ，问 k 次之后变成了哪两个数，对998244353 取模，多组数据。  
思路：模拟一下，算几个数，发现是有规律的，如果k是奇数，结果就是 ( a + b ) ∗ 2 k / 2 m o d    m o , ( a − b + m o ) ∗ 2 k / 2 m o d    m o (a+b)\*2^\{k/2\}\\mod mo,(a-b+mo)\*2^\{k/2\}\\mod mo (a\+b)∗2k/2modmo,(a−b\+mo)∗2k/2modmo,这里a-b需要加一个mo保证他是正数，因为对负数取模还是负数，我在这里卡了好几发。如果k是偶数就是 a k / 2 m o d    m o b k / 2 m o d    m o a^\{k/2\}\\mod mo b^\{k/2\}\\mod mo ak/2modmobk/2modmo就好了，用个快速幂就好了。  
AC代码：

#include <bits/stdc++.h>
    #define ll long long
    using namespace std;
    
    const ll mo = 998244353;
    ll qpow(ll a, ll n,ll m){ 
    	ll ans = 1;
    	while(n){ 
    		if(n&1)
    		{ 
    			ans = a * ans % m;
    		}
    		a = a * a % m;
    		n >>= 1;
    	}
    	return ans;
    }
    void solve()
    { 
        ll a, b, k;
        scanf("%lld%lld%lld",&a,&b,&k);
        ll x = qpow(2,k/2,mo);
        ll ans1, ans2;
    
        if(k%2)
        { 
            ans1 = (a+b)%mo*x%mo;
            ans2 = (a-b+mo)%mo*x%mo;
            printf("%lld %lld",ans1,ans2);
        }
        else
        { 
            ans1 = a%mo*x%mo;
            ans2 = b%mo*x%mo;
            printf("%lld %lld",ans1,ans2);
        }
    }
    int main()
    { 
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    	int t;
    	scanf("%d",&t);
    	for(int i =1;i <= t;i++)
        { 
            solve();
            printf("\n");
        }
        return 0;
    }

# 1002 随机题意 思维 #

题目地址[1002 随机题意][1002]  
题意：给一个整数数组 a1,a2,⋯,an 和 k ，你想要找到一个最大的值 x ，使得存在另一个整数数组 b1,b2,⋯,bn 满足 |ai−bi|≤k(1≤i≤n) 且 bn 中共有 x 个不同的数。  
思路：给定k值后，每给一个数，对应的b值都有一个取值范围，\[ai-k,ai+k\]，把所有区间并到一起求区间长度就可以了。  
AC代码：

/* ** Author: ** Time: ** function: */
    #include <bits/stdc++.h>
    #define ll long long
    using namespace std;
    struct qujian{ 
        int l,r;
        bool operator<(const qujian& a)const
        { 
            return l > a.l;
        }
    };
    void solve()
    { 
        int n, k;
        cin >> n >> k;
        priority_queue<qujian> pqq;
        vector<qujian> vq;
        for(int i = 1;i <= n;i++)
        { 
            int a;
            qujian q;
            cin >> a;
            q.l = a - k;
            q.r = a + k;
            pqq.push(q);
        }
        for(int i = 1;i <= n;i++)
        { 
            qujian q1 = pqq.top();
            pqq.pop();
            if(pqq.empty())
            { 
                vq.push_back(q1);
                break;
            }
            else
            { 
                qujian q2 = pqq.top();
                if(q1.r >= q2.l)
                { 
                    q1.r = q2.r;
                    pqq.pop();
                    pqq.push(q1);
                }
                else
                { 
                    vq.push_back(q1);
                }
            }
        }
        ll ans = 0;
        for(int i = 0;i < vq.size();i++)
        { 
            ans += vq[i].r-vq[i].l+1;
        }
        if(ans > n)
        { 
            cout << n << endl;
        }
        else
        cout << ans << endl;
    }
    int main()
    { 
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    	cin.sync_with_stdio(0);
    	cin.tie(0);
        int t;
        cin >> t;
        while(t--)
        { 
            solve();
        }
        return 0;
    }

# 1003 魔怔 图论 欧拉回路 #

题目地址[1003 魔怔][1003]

参考地址 [2021 年百度之星·程序设计大赛 - 初赛二 1003 魔怔（并查集，联通性，欧拉回路）][2021 _ - _ 1003]  
AC代码：

//没补完.jpg
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    const int maxn = 1010;
    
    int fa[maxn+10];
    void init(int n){ for(int i = 1; i <= n; i++)fa[i]=i;}
    int find(int x){ return x==fa[x]?x:fa[x]=find(fa[x]);}
    void merge(int x, int y){ x=find(x);y=find(y);if(x!=y)fa[x]=y;}
    
    int e[maxn][maxn], in[maxn];
    
    int main(){ 
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int T;  cin>>T;
        while(T--){ 
            memset(e,0,sizeof(e));
    		memset(in,0,sizeof(in));
            
            int n, rt;  cin>>n>>rt;
            int cnt = 0;  init(n);
            for(int i = 2; i <= n; i++){ 
                string s;  cin>>s;
                for(int j = 0; j < i-1; j++){ 
                    e[i][j+1] = e[j+1][i]= s[j]-'0';
                    if(e[i][j+1]==0){ 
                        cnt++;   
                        in[i]++;  in[j+1]++;//累加度数
                        merge(i,j+1);
                    }
                }
            }
            //cout<<cnt+2<<"\n";
            
            LL ans = 0, sum = 0, ok=0;
            map<int,int>mp;
            for(int i = 1; i <= n; i++){ 
                if(in[i]%2==1)ans++;
                sum += in[i];
                if(in[i]){ 
                    int s = find(i);
                    if(mp[s]==0){ ok++; mp[s]=1;}
                }
            }
            if(sum==0){ cout<<"0\n"; continue;}
            sum = sum/2+(ok-1)*2;
            if(ans>2){ cout<<"-1\n"; continue;}
            else{ 
                if(in[rt]){ //在
                    if(in[rt]%2==0){ //偶数
                        if(ans)cout<<"-1\n";
                        else cout<<sum<<"\n";
                    }else{ //奇数
                        cout<<sum<<"\n";
                    }
                }else{ //不在
                    if(ans==0)cout<<sum+2<<"\n";
                    else cout<<"-1\n";
                }
            }
            
            
            continue;
            for(int i = 1; i <= n; i++){ 
                for(int j=1; j <= n; j++)cout<<e[i][j]<<" ";
                cout<<"\n";
            }
        }
        
        return 0;
    }

# 1004 净化 数学，思维 #

[1004 净化][1004]  
思路：找规律，用 s u m n sum\_n sumn表示前n项和，分两种情况， s u m n sum\_n sumn>0和 s u m n sum\_n sumn<=0  
 s u m n sum\_n sumn>0：分两种情况  
每一个 s u m i sum\_i sumi>=0，第一轮初值为0，后面初值都每次增加 s u m n sum\_n sumn,注意不一定是 s u m n sum\_n sumn最大，可能是 s u m i sum\_i sumi  
存在 s u m i sum\_i sumi小于零，将最小的 s u m i sum\_i sumi记录下来minx,第一轮初值为零，第二轮初值为 s u m n sum\_n sumn\-min,后面初值每次增加 s u m n sum\_n sumn

s u m n sum\_n sumn<=0：  
第一轮初值为0，第二轮初值为 s u m n sum\_n sumn\-minx,后面每轮初值跟第二轮相同

/* ** Author: ** Time: ** function: */
    #include <bits/stdc++.h>
    #define ll long long
    const int maxn = 1e5+5;
    using namespace std;
    ll sum1[maxn],sum12[maxn];
    ll sum2[maxn];
    int a[maxn];
    
    void solve()
    { 
        int n;
        ll m;
        bool flag = false;
        cin >> n >> m;
        ll minx = 0,maxx = 0;
        for(int i = 1;i <= n;i++)//直接暴力求第一轮的结果
        { 
    
            cin >> a[i];
            sum1[i] = sum1[i-1] + a[i];//变零
            sum12[i] = sum12[i-1]+a[i];//不变零
            if(sum1[i] < 0)
            { 
                sum1[i] = 0;
            }
            maxx = max(maxx,sum12[i]);
    
            if(sum1[i] >= m)
            { 
                flag = 1;
            }
        }
        if(flag)
        { 
            cout << 1 << endl;
            return;
        }
        ll ans = 0;
        ll b = sum1[n];//第二轮的初值是第一轮的末尾值,此后每轮增加sum12[n]
        if(sum12[n] > 0)
        { 
            if(maxx + b>=m)
            { 
                ans = 2;
            }else
            { 
                ans = ceil((m - maxx - b * 1.0)/(sum12[n])) + 2;
            }
        }
        else
        { 
            b = sum1[n];
            sum2[0] = b;
            for(int i = 1;i <= n;i++)
            { 
                sum2[i] = sum2[i-1] + a[i];
                if(sum2[i] < 0)
                { 
                    sum2[i] = 0;
                }
                if(sum2[i] >= m)
                { 
                    ans = 2;
                }
            }
            if(!ans)
            { 
                ans = -1;
            }
        }
        cout << ans << endl;
        memset(sum1,0,sizeof(sum1));
        memset(sum2,0,sizeof(sum2));
    }
    int main()
    { 
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    	cin.sync_with_stdio(0);
    	cin.tie(0);
        int t;
        cin >> t;
        while(t--)
        { 
            solve();
        }
        return 0;
    }

[2021 _ -]: https://acm.hdu.edu.cn/search.php?field=problem&key=2021+%C4%EA%B0%D9%B6%C8%D6%AE%D0%C7%A1%A4%B3%CC%D0%F2%C9%E8%BC%C6%B4%F3%C8%FC+-+%B3%F5%C8%FC%B6%FE&source=1&searchmode=source
[2021 _ - 1]: http://bestcoder.hdu.edu.cn/contests/contest_show.php?cid=999
[1001]: http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=999&pid=1001
[1002]: https://acm.hdu.edu.cn/showproblem.php?pid=7005
[1003]: https://acm.hdu.edu.cn/showproblem.php?pid=7006
[2021 _ - _ 1003]: https://gwj1314.blog.csdn.net/article/details/119357806?utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EOPENSEARCH%7Edefault-4.base&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EOPENSEARCH%7Edefault-4.base
[1004]: https://acm.hdu.edu.cn/showproblem.php?pid=7007