LOADING

加载过慢请开启缓存 浏览器默认开启

codeforces792BCD

这么好的日子宅寝室写题解
QAQ

B:

题意:输入题目给定的a,b,c,(其中a<b<c)求三个值x,y,z 使得满足

x mod y = a, 1

y mod z = b, 2

z mod x = c 3

输出任何满足条件的x,y,z

题解:要求任意满足条件的三个值互相取模得到输入值,我们不妨假设一个输出的值就是其对应的输入值,如y=b,此时要求得另外两解,我们可以对a和c进行调用,我们可以发现以下规律,但是这会有一个特殊情况,因为c使最大的,所以 a+b+c<3*c,a+b+c 可能是 a+b 的整数倍 ,所以固定y值时可能出现第三个条件不满足的情况,所以我们应该固定最大的z对应的c值。

#include<iostream>
using namespace std;
void solve()
{
    int a,b,c;cin>>a>>b>>c;
    cout<<a+b+c<<' '<<b+c<<' '<<c<<endl;
}
int main()
{
    int n;cin>>n;
    while(n--)solve();
}

C :

题意:

对每组数据输入 n * m (1 ≤ n, m ≤ 2⋅10^5 )的矩阵,其中每个位置的值不超过10^9,要求对换两列元素使得矩阵每行非递增,输出对调的两列下标,若不存在满足情况的两列则输出 -1

题解:

先找到任一 一行的非递减的的位置下标存入数组bb,记该行不满足的下标数量为num,若num大于2则直接输出 -1,若 num==0 即矩阵本就满足情况,输出1 1,若以上情况都不存在即num==2的时候,对调矩阵中每行该下标位置的元素值,然后遍历每一行元素判断是否非递减排列,若不满足输出-1,否则最后输出 两个下标位置。

#include <bits/stdc++.h>
#define rep(i,n,m) for(int i=n;i<=m;++i)
#define per(i,n,m) for(int i=n;i>=m;--i)
using namespace std;
typedef long long ll;;
void solve()
{
    int n,m;cin>>n>>m;
    vector<vector<int>> a(n,vector<int>(m));
    vector<int> bb;
    rep(i,0,n-1)
        rep(j,0,m-1)
            cin>>a[i][j];   //输入每个元素值
        
    for(int i=0;i<n&&bb.empty();++i){   
        //当下标越界或者该行发现有不满足条件的元素出现时跳出
        vector<int> b=a[i];
        sort(b.begin(),b.end());  //对数组b排序,然后对原数值进行比较
        for(int j=0;j<m;++j){
            if(a[i][j]!=b[j])bb.push_back(j);  //加入不满足的下标
        }
    }
    if(bb.size()==0){cout<<1<<' '<<1<<endl;return ;}  //不存在不满足的情况
    else if(bb.size()>2){cout<<-1<<endl;return ;}   //不满足的情况太多,>2
    rep(i,0,n-1)swap(a[i][bb[0]],a[i][bb[1]]);    //否则交换两列数值
    rep(i,0,n-1){
        rep(j,0,m-2){
            if(a[i][j]>a[i][j+1]){       //判断是否满足条件
                cout<<-1<<endl;
                return ;
            }
        }
    }
    cout<<bb[0]+1<<' '<<bb[1]+1<<endl;  //因为记的下标是从0开始的,所以记得+1
    
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;
    while(n--)solve();
    return 0;
}

天啦噜,昨晚开a【200001】【200001】的数组爆栈了,麻木了我一个多小时,今天学到了个新招 ,用vector 开二维,就 vector<vector> a(n,vector(m)); 这样写,是 n * m 的二维数组。

D

题意:每组数据给定 n 个陷阱的伤害值,k 次跳越一个陷阱的机会,每跳过一个陷阱,后面所有的陷阱伤害值都会 +1,求经过所有陷阱后所受伤害的 最小值。

题解:

当所有的陷阱都要跳进去时,所受伤害就是每个陷阱伤害值的和 ans,对于每一个陷阱,如果跳过当前的陷阱,对于整体所受的伤害 ans 就是 ans = ans - a [ i ] +( n - i ) = n - i - a [ i ] ,而对于当前跳的第 j 个陷阱,若跳过该陷阱 ,后面还有 k - j 次机会可以跳,即还有k - j 个陷阱的+1 不用算到ans之中去,所有对于k次机会,一共有 (k - 1)*k / 2点伤害不用承受。

我们只需求出跳越每个陷阱对整体所减少的伤害值,并贪心求最大减伤即可。

#include <bits/stdc++.h>
#define rep(i,n,m) for(int i=n;i<=m;++i)
#define per(i,n,m) for(int i=n;i>=m;--i)
//#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N=200010;
void solve()
{
    ll n,k,ans=0;cin>>n>>k;
    
    vector< ll >a(n);
    
    for(int i=0;i<n;++i){
        int x;cin>>x;
        ans+=x;      //计总伤害值
        a[i]=1LL*(n-i-1-x);   //记得取1LL,不然会超范围
    }        
    sort(a.begin(),a.end());  
 
    rep(i,0,k-1)  ans+=a[i];  //贪心使伤害最小化
 
    cout<< ans - ( k * (k-1) / 2 )<<endl;  //减去对当前跳过的陷阱后面跳过的陷阱+1的伤害
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;cin>>n;
    while(n--)solve();
    return 0;
}

cf分天天掉,上绿还没稳住一直拼命往下掉,蒻苟本狗