牛客小白77

题一

暴力做法

#include<bits/stdc++.h>
using namespace std;
#define for1(i,a,b) for(int i=(a);i<=(b);i++)
#define for2(i,a,b) for(int i=(a);i>=(b);i--)
typedef long long LL;
typedef pair<int,int>PII;
typedef pair<double,double>PDD;
typedef unsigned long long ULL;
typedef pair<long long,int> PLI;
const int N = 2e3+10,M=1e5+10;
const int mod = 100003;
int a[100][100];
int n,m;
int main()
{
	ios::sync_with_stdio(false);
	for1(i,1,2){
		for1(j,1,2){
			cin>>a[i][j];
		}
	}
	int ok=0;
	for1(i,1,2){
		for1(j,1,2){
			for1(k,0,9){51//暴力枚举，改变a数组的数值，由于题目规定a数组中的数范围为1到9
				int sv=a[i][j];
				a[i][j]=k;
				set<int> st;
				st.insert(a[1][1]+a[1][2]);
				st.insert(a[2][2]+a[1][2]);
				st.insert(a[2][2]+a[2][1]);
				st.insert(a[1][1]+a[2][1]);
				if(st.size()==1) ok=1;
				a[i][j]=sv;//还原
			}
		}
	}
	if(ok) cout<<"YES";
	else cout<<"NO";
	return 0;
}

标准做法

如果对角线相等，则YES，否则NO。

#include<bits/stdc++.h>
using namespace std;
#define for1(i,a,b) for(int i=(a);i<=(b);i++)
#define for2(i,a,b) for(int i=(a);i>=(b);i--)
typedef long long LL;
typedef pair<int,int>PII;
typedef pair<double,double>PDD;
typedef unsigned long long ULL;
typedef pair<long long,int> PLI;
const int N = 2e3+10,M=1e5+10;
const int mod = 100003;
int a[100][100];
int n,m;
int main()
{
	ios::sync_with_stdio(false);
	for1(i,1,2){
		for1(j,1,2){
			cin>>a[i][j];
		}
	}
	int ok=0;
	if(a[1][1]==a[2][2]||a[1][2]==a[2][1]) ok=1;
	if(ok) cout<<"YES";
	else cout<<"NO";

	return 0;
}

题二

链接

#include<bits/stdc++.h>
using namespace std;
#define for1(i,a,b) for(int i=(a);i<=(b);i++)
#define for2(i,a,b) for(int i=(a);i>=(b);i--)
typedef long long LL;
typedef pair<int,int>PII;
typedef pair<double,double>PDD;
typedef unsigned long long ULL;
typedef pair<long long,int> PLI;
const int N = 2e3+10,M=1e5+10;
const int mod = 100003;
int a[100][100];
int n,m;
int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>m;
	cout<<n-m;

	return 0;
}

题三差分维护序列的相交点，输出相交最多的点向上整除K 题三

#include<bits/stdc++.h>
using namespace std;
#define for1(i,a,b) for(int i=(a);i<=(b);i++)
#define for2(i,a,b) for(int i=(a);i>=(b);i--)
typedef long long LL;
typedef pair<int,int>PII;
typedef pair<double,double>PDD;
typedef unsigned long long ULL;
typedef pair<long long,int> PLI;
const int N = 1e6+10,M=1e5+10;
const int mod = 100003;
int a[N];
int n,m,k;
int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>m>>k;
	for1(i,1,m){
		int x,y;
		cin>>x>>y;
		a[x]++,a[y]--;
	}
	int res = 0;
	for1(i,1,n){
		a[i]+=a[i-1];
		res=max(res,a[i]);
	}
	cout<<(res+k-1)/k;
	return 0;
}

题六

链接
本题解法为：从数据考虑，发现1e12太大，这诱使我们往根号的方向想，
先dp处理1到1e6的数据.详情看代码注释，f[x]表示从i到x所需要的最小次数

#include<bits/stdc++.h>
using namespace std;
#define for1(i,a,b) for(int i=(a);i<=(b);i++)
#define for2(i,a,b) for(int i=(a);i>=(b);i--)
typedef long long LL;
typedef pair<int,int>PII;
typedef pair<double,double>PDD;
typedef unsigned long long ULL;
typedef pair<long long,int> PLI;
const int N = 1e6+10,M=1e5+10;
const ULL base = 131;
map<LL,LL> dp;
LL f[N],a,b;

LL dfs(LL x)
{
	if(x<=sqrt(b)) return f[x];
	if(x<a) return 0x3f3f3f3f;
	if(dp.count(x)) return dp[x];//表明已经找到到x的最小次数
	LL sqr=sqrt(x);
	dp[x]=x-a;
	if((x>>1)>=a) dp[x]=min(dp[x],dfs(x/2)+x%2+1);
	if(sqr>=a) dp[x]=min(dp[x],dfs(sqr)+x-(sqr*sqr)+1);
	return dp[x];
}
int main()
{
	ios::sync_with_stdio(false);
	int t;
	cin>>t;
	while(t--)
	{
		dp.clear();//多组数据记得清空
		cin>>a>>b;
//         if(a>b){
//             cout<<-1<<endl;
//             continue;
//         }
        if(a==b) {
            cout<<0<<endl;;
            continue;
        }
		if(a<N) f[a]=0;
		for(LL i=a+1;i<=sqrt(b);i++){
			f[i]=f[i-1]+1;
			if(!(i&1)&&(i>>1)>=a) f[i]=min(f[i],f[i>>1]+1);//i能整除2，
			LL sqr=sqrt(i);
			if(sqr*sqr==i&&sqr>=a) f[i]=min(f[i],f[sqr]+1);//sqr*sqr==i;
		}
		cout<<dfs(b)<<endl;
	}
	return 0;
}