A. 小田的同余

题目类型：模拟

思路

首先通过题意可得知，m为奇数，而2x%m等于1，那2x的最小数就为m+1，最后就可得出公式：x=(m+1)/2，在这道题目中也不用考虑m=1，因为m的数据范围为3≤m≤1000000000000，但是注意：m要开long long，而最后的结果也要开long long。

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
	freopen("mod.in","r",stdin);
	freopen("mod.out","w",stdout);
	long long m;
	cin>>m;
	long long x=(m+1)/2;
	cout<<x;
	return 0;
}

本题代码已AC，下一次继续保持。

B. 小田的奶牛要饿坏啦！！

题目类型：模拟

思路

这道题目可以用ans表示有几天不能吃草，res表示能吃几天草，根据这些再来遍历，每次更新ans，res，最后输出t-ans与0的最大值即可，但是注意：所有的变量都要开long long，在更新最大值的时候也要将0变为long long类型。

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
	freopen("cow.in","r",stdin);
	freopen("cow.out","w",stdout);
	long long n,t,ans=0,res=0;
	cin>>n>>t;
	for(long long i=1;i<=n;i++){
	   long long d,b;
	   cin>>d>>b;
	   if(res>=d) res+=b;
	   else ans+=(d-res-1),res=d+b-1;
	}
	cout<<max((long long)0,t-ans);
	return 0;
}

这道题目在写的时候忘写一种特别的情况了了，导致只得了15分，下一次要注意特别的情况。

C. 小田喂猫

题目类型：前缀和加后缀和加二分

思路

这道题如果只用模拟，必定会超时，我们看，其实k天吃的猫粮总数中若猫粮数量大于k，那k天就会吃k次，若猫粮数量小于k，那k天就会吃猫粮的数量，但用这个方法来写代码还是会超时，我们再看可以发现猫粮可以分成两个部分，第一个部分是在k天之内可以吃完，第二个部分是在吃了k天后还有剩余的，那么在他们之间就必定有一个整数k，来分割他们两部分，而必定会满足这样一个性质：k与k的前面必定在k天之内可以吃完，在k的后面必定在吃了k天后还有剩余的，我们要可以用二分找到这个数，那就是找出<=k的最后一个数，那就要用二分的第二个模板，除此之外，我们还要使用前缀和来计算区间和，然后用二分找到这个数，最后将他们两加起来输出即可，但是数据不一定保证升序，所以在处理之前还要将数据进行升降排序排序，注意：为了方便我们可以用pair，但是在输入的时候我们要将营养值定为pair的第二项，将数量定为pair的第一项，因为我们要看的不是营养值，而是数量，在排序的时候也会看第一项的值（也就是数量），再其次就是要开long long.

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
pair<long,long> a[N];
long long s[N],b[N];
int k;
long long ef(int l,int r){ 
    while(l<r){  
        long long mid=(l+r+1)/2;
        if(a[mid].first<=k) l=mid;  
        else r=mid-1;  
    }  
    return l;  
}  
int main(){
	freopen("cat.in","r",stdin);
	freopen("cat.out","w",stdout);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i].second;
	for(int i=1;i<=n;i++) cin>>a[i].first;
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i].first*a[i].second;
	for(int i=n;i>=1;i--) b[i]=b[i+1]+a[i].second;
	int q;
	cin>>q;
	while(q--){
		cin>>k;
		long long d=ef(0,n);
		cout<<s[d]+b[d+1]*k<<endl;
	}
    return 0;
}

这道题目在写的时候写了暴力，只拿了30分，下次要想一想AC的写法。

D. 小田的打字练习

题目类型：模拟

思路

这道题目就是一个大模拟，只需注意处理退格键，其他按题目要求来就行。

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
	freopen("key.in","r",stdin);
	freopen("key.out","w",stdout);
	string s;
	vector<char> a,b;
	while(getline(cin,s)){
		if(s=="EOF") break;
		if(s==" ") continue;
		for(int i=0;i<s.size();i++){
			if(s[i]=='<'&&s[0]!='<') a.pop_back();
			if(s[i]!='<') a.push_back(s[i]);
		}
		a.push_back('>');
    } 
	while(getline(cin,s)){
        if(s=="EOF") break;
        if(s=="") continue;
        for(int i=0;i<s.size();i++){
            if(s[i]=='<'&&s[0]!='<') b.pop_back();
            if(s[i]!='<') b.push_back(s[i]);
        }
        b.push_back('>');
    }
	int cnt=0;
	for(int i=0,j=0;i<a.size()&&j<b.size();i++,j++){
		while(a[i]=='>'&&b[j]!='>') j++;
		while(a[i]!='>'&&b[j]=='>') i++;
		if(a[i]==b[j]&&a[i]!='>') cnt++;
	}
	double n;
	cin>>n;
	n/=60;
	cout<<(long long)(cnt/n+0.5);
	return 0;
}

这道题目在写的时候忘写一种特别的情况了了，导致只得了45分，下一次要注意特别的情况。

E. 小田切蛋糕

题目类型：前缀和加二分

思路

对于这道题目，我们先可以一个一个去枚举巧克力碎屑的数量，再来计算是否可行，所以我们不妨用前缀和来写，但是我们会发现，这么写是会超时的，所以我们还需要用二分。

代码

#include<bits/stdc++.h>
using namespace std;
int d[510][510],s[510][510],r,c,a,b;
int check(int mid){
	int l1=0,r1=0;
	for(int i=1;i<=r;i++){
		int x=0,y=0;
		for(int j=1;j<=c;j++){
			int f=s[i][j]-s[i][x]-s[r1][j]+s[r1][x];
			if(f>=mid) x=j,y++;
			if(y==b){
			    l1++,r1=i;
			    break;
			}
		}
		if(l1==a)return 1;
	}
	return 0;
}
int ef(int e){
	int l=0,r=e;
	while(l<r){
		int mid=l+r+1>>1;
		if(check(mid)) l=mid;
		else r=mid-1;
	}
	return l;
}
int main(){
	freopen("cake.in","r",stdin);
	freopen("cake.out","w",stdout);
	int e;
	cin>>r>>c>>a>>b;
	for(int i=1;i<=r;i++) 
	    for(int j=1;j<=c;j++){
	    	cin>>d[i][j];
	    	s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+d[i][j];
	    	if(i==r&&j==c) e=s[i][j];
		}
	int cnt=ef(e);
	cout<<cnt;
	return 0;
}

这道题目完全没有思路，所以就放弃了，输出了个-1骗了十五分，下一次不能轻易放弃。

F. 小田想困住奶牛

题目类型：模拟

思路

每次模拟一下，只要让牛往左走或者让牛往右走即可，最后判断一下，若ans没变，输出-1，否则输出0与ans的最大值。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
pair<int,int> a[N];
int main(){
	freopen("cow.in","r",stdin);
	freopen("cow.out","w",stdout);
	int n,b,nl,nr;
	cin>>n>>b;
	for(int i=1;i<=n;i++) cin>>a[i].second>>a[i].first;
	sort(a+1,a+1+n);
	int ans=1e9;
	for(int i=1;i<=n;i++){
		if(a[i].first>b){
			nr=i; 
			nl=i-1;
			break;
		} 
	}
	long long l=nl,r=nr;
    if(b>a[n].first||b<a[1].first){
		cout<<-1;
		return 0;
	}
	while(l>=1){
		while(r<=n&&a[r].first-a[l].first>a[r].second) r++;
		if(r>n) break;
		ans=min(ans,a[r].first-a[l].first-a[l].second);
		l--;
	}
	l=nl,r=nr;
	while(r<=n){
		while(l>=1&&a[r].first-a[l].first>a[l].second) l--;
		if(l<1) break;
		ans=min(ans,a[r].first-a[l].first-a[r].second);
		r++;
	}
	if(ans==1e9) cout<<-1;
	else cout<<max(0,ans);
	return 0;
}

这道题目完全没有思路，所以就放弃了，下一次不能轻易放弃。