AcWing春季每日一题

1.AcWing 3346. 你知道你的ABC吗2.AcWing 3358. 放养但没有完全放养3.AcWing 3370. 牛年4.AcWing 3745. 牛的学术圈 I5.AcWing 1459. 奶牛体操6.AcWing 1442. 单词处理器7.AcWing 1671. 三角形8.AcWing 1659. 社交距离 I9.AcWing 1714. 混合牛奶10.AcWing 1695. 果壳游戏11.AcWing 1683. 困牛放牧12.其他的一些题AcWing 105.七夕祭

题目

AC代码：

#include 
#include 
#include 
using namespace std;
int a[10],x,y,z,sum;
bool cmp(int x,int y){
    return x 
2.AcWing 3358. 放养但没有完全放养 
题目
 
AC代码：
 
#include 
#include 
#include 
using namespace std;
char s[1010],a[1010];
int main(){
    scanf("%s",s);
    scanf("%s",a);
    int ls = strlen(s);
    int la = strlen(a);
    int k=0,sum=0,flag=0;
    while(1){
        sum++;
        for(int i=0;i 
3.AcWing 3370. 牛年 
题目
 
AC代码：
 
#include
using namespace std;
long long n,i,j,x;
string a,b,c,d;
string an[13]={"Ox","Tiger","Rabbit","Dragon","Snake","Horse","Goat","Monkey","Rooster","Dog","Pig","Rat"};//初始化
map year;
int main()
{
    year["Bessie"]=0;//初始化
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>a>>b>>b>>b>>c>>d>>d>>d;//读掉一些不需要的东西
        if(b=="previous")
        {
            for(j=year[d]-1;;j--)   if(an[(j%12+12)%12]==c) break;//查找年份
            year[a]=j;
        }
        else
        {
            for(j=year[d]+1;;j++)   if(an[(j%12+12)%12]==c) break;//查找年份
            year[a]=j;
        }
    }
    cout< 
4.AcWing 3745. 牛的学术圈 I 
题目
 
AC代码：
 
#include 
#include 
#include 
using namespace std;
const int N = 1e5+10;
int n,l;
int c[N];
bool cmp(int a,int b){
	return a > b;
}
int main(){
	scanf("%d %d",&n,&l);
	for(int i=1;i<=n;i++)
		scanf("%d",&c[i]);
	sort(c+1,c+1+n,cmp);
	int maxx=0;
	for(int i = 1;i<=n;i++){	 
		if(c[i] >= i)
			maxx=i;
		else
			break;
	} 
	if(c[maxx + 1] < maxx){
		printf("%dn",maxx);
		return 0;
	} 
	int sum=0;
	for(int i=1;i<=maxx+1;i++)
		if(c[i] == maxx)
		sum++;
	if(sum > l)
		printf("%dn",maxx);
	else	
		printf("%dn",maxx+1);
	return 0;
} 
 
5.AcWing 1459. 奶牛体操 
题目
 
AC代码：
 
#include 
#include 
#include 
using namespace std;
int a[30],b[30][30];
int main(){
	int n,k;
	scanf("%d %d",&k,&n);
	for(int i=1;i<=k;i++){
		for(int j=1;j<=n;j++)
			scanf("%d",&a[j]);
		for(int j=1;j 
6.AcWing 1442. 单词处理器 
题目
 
AC代码：
 
#include 
using namespace std;
int n,k,v=1,la = 0;
char s[20],a[100][100];
int main(){
 	scanf("%d %d",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%s",s);
		int ls = strlen(s);
		if (la + ls > k){
			for(int j=1;j 
7.AcWing 1671. 三角形 
题目
 
AC代码：
 
#include 
using namespace std;
int n,maxx = 0;
int x[110],y[110];
int find(int p){
	int h=0,a=0,area=0;
	for(int i=1;i<=n;i++){
		if(i == p)
			continue;
		if(x[i] == x[p])
			a = max(a,abs(y[p]-y[i]));
		if(y[i] == y[p])
			h = max(h,abs(x[p]-x[i]));
		area = max(area,a*h);	
	}
	return area;
}
int main(){
 	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d %d",&x[i],&y[i]);
	for(int i=1;i<=n;i++)
		maxx = max(maxx,find(i));
	printf("%dn",maxx);
	return 0;
}
 
8.AcWing 1659. 社交距离 I 
题目
 
AC代码：
 
#include
using namespace std;

const int N=100005;
int n,m,ans;
int a[N];
char s[N];


bool check(int x) {
    int p=1-x,cnt=0;//cnt不一定恒等于2，小于2代表方案不合理，大于等于2代表方案合理 
    for(int i=1; i<=m; i++) {
        while(p+x+x<=a[i]) p+=x,cnt++;//如果符合条件，p就往后移动x的距离，牛的头数就加一头 
        p=a[i];//令p=a[i],p就是前一头牛的位置 
    }
    while(p+x<=n) p+=x,cnt++; //因为存在插入位置没包含最后一个位置n的情况，所以需要继续往后加牛，直到加到不能加位置 
    return cnt>=2;//如果加入的牛的数量大于等于2，证明我们的方案是可行的，即x是一种答案 
}

int main() {
    cin>>n;
    cin>>s+1;
    for(int i=1; i<=n; i++)
        if(s[i]=='1') a[++m]=i;
    int l=1,r=n;
    for(int i=1; i>1;
        if(check(mid)) {
            ans=mid;
            l=mid+1;
        } else r=mid-1;
    }
    cout< 
9.AcWing 1714. 混合牛奶 
题目
 
AC代码：
 
#include 
#include 
#include 
using namespace std;
int c1,m1,c2,m2,c3,m3,flag=1;
int main(){
	scanf("%d %d %d %d %d %d",&c1,&m1,&c2,&m2,&c3,&m3);
	for(int i=1;i<=100;i++){
		if(flag == 1){
			if(m1 + m2 <= c2){
				m2 = m1 + m2;
				m1 = 0;
			}else{
				m1 = (m1 + m2) - c2;
				m2 = c2;
			}
			flag = 2;
		}else if(flag == 2){	
			if(m2 + m3 <= c3){
				m3 = m2 + m3;
				m2 = 0;
			}else{
				m2 = (m2 + m3) - c3;
				m3 = c3;
			}
			flag = 3;
		}else if(flag == 3){
			if(m3 + m1 <= c1){
				m1 = m1 + m3;
				m3 = 0;
			}else{
				m3 = (m1 + m3) - c1;
				m1 = c1;
			}
			flag = 1;
		}
	}
	printf("%dn%dn%dn",m1,m2,m3);
	return 0;
}
 
10.AcWing 1695. 果壳游戏 
题目
 
AC代码：
 
#include 
#include 
#include 
using namespace std;
int a[10101],b[10101],g[10101],d[101];
int main(){
    int n,flag,maxx = 0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d %d %d",&a[i],&b[i],&g[i]);
	
	for(int i=1;i<=3;i++){
		flag = i;
		d[1]=1;
		d[2]=2;
		d[3]=3;
		int sum=0;
		for(int j=1;j<=n;j++){
			int temp = d[a[j]];
			d[a[j]] = d[b[j]];
			d[b[j]] = temp;
			
			if(d[g[j]] == flag)
				sum++;
		}
		maxx=max(maxx,sum);
	}
	printf("%dn",maxx);
	return 0;
}
 
11.AcWing 1683. 困牛放牧 
题目
 
AC代码：
 
#include 
#include 
#include 
using namespace std;
int main(){
	int a,b,c,d1,d2;
	scanf("%d %d %d",&a,&b,&c);
	d1=b-a-1;
	d2=c-b-1;
	if(d1 == 0 && d2 == 0)
		printf("0n0n");
	else if(d1 == 0 || d2 == 0){
		int t = max(d1,d2);
		if(t == 1)
			printf("1n1n");
		else{
			printf("2n%dn",t);
		}
	}
	else{
	    if(d1 > d2)
	    	swap(d1,d2);
	    if(d1 == 1)
	    printf("1n%dn",d2);
	    else
	    printf("2n%dn",d2);
	}
	return 0;
} 
 
12. 
 
其他的一些题 
AcWing 105.七夕祭 
题目
 思路可参照糖果传递
 AC代码：
 
#include 
#include 
#include 
using namespace std;
const int N = 1e5 + 10;
typedef long long ll;
int C[N],R[N];
int n,m,t;
ll ans = 0;
ll check(int P[],int x){
	int S[N] = {0};
	ll sum = 0;
	ll average = t / x; 
	for(int i=1;i<=x;i++)
		S[i] = S[i-1] + P[i] - average; 
	sort(S+1,S+1+x);
	ll mid = S[(1 + x)/2];
	for(int i=1;i<=x;i++)
		sum += abs(S[i] - mid);
	return sum;
}
int main(){
	scanf("%d %d %d",&n,&m,&t);
	for(int i=1;i<=t;i++){
		int x,y;
		scanf("%d %d",&x,&y);
		R[x]++;
		C[y]++;
	}
	bool flag1,flag2;
	flag1 = flag2 = false;
	if(t % m == 0){
		flag1 = true;
		ans += check(C,m);
	}
	if(t % n == 0){
		flag2 = true;
		ans += check(R,n);
	}
	if(flag1 && flag2)
		printf("both %lldn",ans);
	else if(flag1)
		printf("column %lldn",ans);
	else if(flag2)
		printf("row %lldn",ans);
	else 
		printf("impossiblen");
	return 0;
}