居然Rated!

哇我明天早自习怕不是要被查水表了QAQ

不管了先补下题解

A. Partition

这题很zz你就把正数划到B负数划到C就行了

代码↓

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iterator>
#include<cstdlib>
#include<string>
using namespace std;

int n,seq;
int ans=0;

inline void readx(int& x)
{
	x=0; int k=1; register char ch=0;
	while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }
	while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}

int main()
{
	readx(n);
	for (int i=1;i<=n;i++) 
	{
		readx(seq);
		if (seq>=0) ans+=seq;
		else ans+=(-seq);
	}
	
	printf("%d\n",ans);
	return 0;
}

B. Weird Subtraction Process

这题也很zz,fqk学长推了下式子然而我直接写了个二分

二分(a或b)*2*k可以证明复杂度非常优秀,大概在O(logn)还是怎么着的反正减一次还是减两次就完事了

具体证明等我再补 不一定能记得补

来补

复杂度是O(log2n)

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iterator>
#include<cstdlib>
#include<string>
using namespace std;

long long a,b;

inline void readx(long long& x)
{
	x=0; long long k=1; register char ch=0;
	while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }
	while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}

inline long long BinSearch(long long var,long long num)
{
	long long l=1,r=2*1e18/(num*2),mid=0,ans=0;
	while (l<=r)
	{
		mid=(l+r)>>1;
		if (var==mid*2*num) return mid;
		else if (var>mid*2*num) 
		{
			ans=mid;
			l=mid+1;
		}
		else r=mid-1;
	}
	return ans;
}

int main()
{
	readx(a); readx(b);
	while ((a>=2*b || b>=2*a) && a && b)
	{
		if (a>=2*b) a-=b*BinSearch(a,b)*2;
		else b-=a*BinSearch(b,a)*2;
	}
	printf("%lld %lld\n",a,b);
	return 0;
}

C. String Transformation

贪心。忽略掉z即可

别忘记特判,具体看代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iterator>
#include<cstdlib>
#include<string>
using namespace std;

char seq[100010]={0},ch=0; 
int ctr1=0,ans=0,pos=1;

inline void readx(int& x)
{
	x=0; int k=1; register char ch=0;
	while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }
	while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}

int main()
{
	while (ch<'a' || ch>'z') ch=getchar();
	while (ch>='a' && ch<='z') { seq[++ctr1]=ch; ch=getchar(); }
	
	if (ctr1<26) { printf("-1\n"); return 0; }
	
	for (;pos<=ctr1;pos++)
	{
		if (ans==26)
		{
			for (int i=1;i<=ctr1;i++) printf("%c",seq[i]);
			return 0;
		}
		if (seq[pos]-'a'<=ans) 
		{
			ans++;
			seq[pos]=ans+'a'-1;
		}
		else if (ans==25) ans++;
	}
	if (ans==26)
	{
		for (int i=1;i<=ctr1;i++) printf("%c",seq[i]);
		return 0;
	}
	printf("-1\n");
	return 0;
}

D. Timetable

前三题都是热身题,这才是个正经题

dp。

先设dx[i][j]是第i天逃课j次后的最小度过时间

dp求这个东西,O(nk2) 先枚举每一天,这是显然的

然后枚举用了几次逃课,再meet in the middle,枚举从开头逃了几节然后就能算结尾逃了几节

预处理一下逃了x节之后在第几个小时就可以O(1)算答案了,三层枚举总的是O(nk2)

然后处理出dx就dp,设dp[i][j]是到第i天为止用了j次逃课得到的最短时间

然后枚举i,这也是显然的

枚举一下j,为了更新dp[i][j]你需要枚举当前第i天用了多少次逃课

这样我们就枚举l做为今天逃课数,然后更新dp[i][j]即可。

这题其实长得蛮像新魔法药水

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iterator>
#include<cstdlib>
#include<string>
using namespace std;

int mapx[510][510]={0};
int n,m,k,spos[510],epos[510],dx[510][510]={0};
int lpos[510][510]={0},rpos[510][510]={0},nums[510]={0};
int dp[510][510]={0};
char ch=0;

inline void readx(int& x)
{
	x=0; int k=1; register char ch=0;
	while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }
	while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}

int main()
{
	readx(n); readx(m); readx(k);
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
		{
			ch=0; while (ch<'0' || ch>'9') ch=getchar();
			mapx[i][j]=ch-'0';
		}
	}
	
	for (int i=1;i<=n;i++)
	{
		int ctr1=0;
		for (int j=1;j<=m;j++) if (mapx[i][j]==1) 
		{
			ctr1++;
			lpos[i][ctr1]=j;
		}
		nums[i]=ctr1;
		ctr1=0;
		for (int j=m;j>=1;j--) if (mapx[i][j]==1)
		{
			ctr1++; rpos[i][ctr1]=j;
		}
	}
	
	memset(dx,0x3f,sizeof(dx));
	for (int i=1;i<=n;i++)
		for (int j=0;j<=k;j++) if (j<nums[i])
			for (int l=0;l<=j;l++) dx[i][j]=min(dx[i][j],rpos[i][j-l+1]-lpos[i][l+1]+1);
	for (int i=1;i<=n;i++) dx[i][nums[i]]=0;
	
	/*
	for (int i=1;i<=n;i++)
	{
		for (int j=0;j<=k;j++) printf("%d ",dx[i][j]);
		printf("\n");
	}*/
	
	
	for (int i=1;i<=n;i++)
	{
		for (int j=0;j<=k;j++)
		{
			dp[i][j]=dp[i-1][j]+dx[i][0];
			for (int l=1;l<=j;l++) dp[i][j]=min(dp[i][j],dp[i-1][j-l]+dx[i][l]);
		}
	}
	printf("%d\n",dp[n][k]);
	return 0;
}

后面三题没做出来 QAQ很惭愧

还是自己太弱了。

分类: Codeforces

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.