- #A.Grade Allocation https://codeforces.com/contest/1316/problem/A
- # 题意
签到, 给定 n 个数, m 为最大值, 平均数必须保持不变, 求能取得的最大值
- # 题解
- ans=min(m,sum)
- #include <bits/stdc++.h>
- #define ll long long
- #define pii pair<int,int>
- #define pll pair<ll,ll>
- #define fi first
- #define se second
- #define pb push_back
- using namespace std;
- const int N=1e5+10;
- int a[N];
- void solve(){
- int n,m;
- cin>>n>>m;
- int sum=0;
- for(int i=1;i<=n;i++){
- cin>>a[i];
- sum+=a[i];
- }
- if(sum>=m)
- cout<<m<<endl;
- else{
- cout<<sum<<endl;
- }
- }
- int main(){
- int t;
- cin>>t;
- while(t--){
- solve();
- }
- }
- # B.String Modification https://codeforces.com/contest/1316/problem/B
- # 题意
一个字符串, 可以执行的操作是一个数 k(1<=k<=n) , i 从 1 到 n-k+1, 将 s[i~i+k-1] 所有 reverse, 求出一个 k 来使得操作后的字符串是字典序最小的, 如果有多个满足的 k, 求最小的 k
# 题解
首先我们有一个字符串 s,
我们可以把它表示为 s1s2s3...sn, 然后我们选择一个 k:
经过第一次反转: sksk−1sk−2...s1sk+1sk+2...sn
观察到之后 sk 的位置就不会发生变化了.
经过第二次反转: sksk+1s1...sk−2sk−1sk+2...sn 观察到之后 sksk+1 的位置都不会发生变化.
经过第三次反转: sksk+1sk+2...s2s1sk+3...sn 观察到之后 sksk+1sk+2 的位置不会再发生变化.
......
以此类推, 最后反转变换过后的字符串 s' 前 n−k+1 个字符一定是 sksk+1sk+2...sn
通过观察还可发现, s 中的前 k−1 个字符 s1s2s3...sk−1 一定会被搬到 s' 的后半部分, 但是方向不确定.
反转次数是 n−k+1, 当反转次数是奇数最后拼接的需要反转, 偶数直接拼接
时间复杂度 O(N2)
- #include<bits/stdc++.h>
- using namespace std;
- int T,n,ans;
- string s,mn;
- string work(int k)
- {
- if(k==n)
- {
- string res=s;
- reverse(res.begin(),res.end());
- return res;
- }
- int t=n-k+1;
- if(t%2==0)
- {
- string res=s.substr(k-1,n-k+1);
- res+=s.substr(0,k-1);
- return res;
- }
- string res=s.substr(k-1,n-k+1);
- string tmp=s.substr(0,k-1);
- reverse(tmp.begin(),tmp.end());
- res=res+tmp;
- return res;
- }
- int main()
- {
- scanf("%d",&T);
- while(T--)
- {
- scanf("%d",&n);
- cin>>s;
- ans=1,mn=s;
- for(int i=2;i<=n;i++)
- if(work(i)<mn)
- mn=work(i),ans=i;
- cout<<mn<<endl<<ans<<endl;
- }
- }
- # C
- # 题意
- # 题解
- # D
- # 题意
- # 题解
- # E
来源: http://www.bubuko.com/infodetail-3449167.html