Lut本科回忆录

这么好的日子宅寝室写题解
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，若 num0 即矩阵本就满足情况，输出1 1，若以上情况都不存在即num2的时候，对调矩阵中每行该下标位置的元素值，然后遍历每一行元素判断是否非递减排列，若不满足输出-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分天天掉，上绿还没稳住一直拼命往下掉，蒻苟本狗