Codeforces Round #567 (Div. 2)

题目链接：http://codeforces.com/contest/1181

A Chunga-Changa

题意：两个人各a,b元，一个物品价值c元,求两个人一起最多可以买多少该物品，以及两人之间最小需要传递多少元。

#include
using namespace std;
#define ll long long
int main()
{
	ll a,b,c;
	while(~scanf("%I64d%I64d%I64d",&a,&b,&c)){
		ll d=(a+b)/c;
		ll e;
		if((a/c+b/c)==d)
			e=0;
		else{
			
			e=min(c-a%c,c-b%c);
		}
		printf("%I64d %I64d\n",d,e);
	}
	return 0;
}

B Split a Number

题意：把一个无前缀0的数拆成两个无前缀0的数，将这两个数相加，求最小结果。

#include
using namespace std;
#define ll long long
const int maxn=100010;

char s[maxn];
char a[maxn],b[maxn];
char c[maxn],c2[maxn];
int n;
void cal2(char c[],char c2[])
{
	int m1=strlen(c),m2=strlen(c2);
	if(m1>m2) return;
	bool flag=0;
	for(int i=m1-1;i>=0;i--){
		if(c[i]!=c2[i]){
			if(c[i]>c2[i])
				flag=1;
			break;
		}
	}
	if(flag)
		memcpy(c,c2,sizeof(c2));
}
void cal(char c[],int m)// a+b->c
{
//	memset(a,0,sizeof(a));
//	memset(b,0,sizeof(b));
	for(int i=0;i=0){
		c[tot++]=(a[i]-'0'+b[j]-'0'+flag)%10+'0';
		flag=(a[i]-'0'+b[j]-'0'+flag)/10;
		i--;j--;
	}
	while(i>=0){
		c[tot++]=(a[i]-'0'+flag)%10+'0';
		flag=(a[i]-'0'+flag)/10;
		i--;
	}
	while(j>=0){
		c[tot++]=(b[j]-'0'+flag)%10+'0';
		flag=(b[j]-'0'+flag)/10;
		j--;
	}
	c[tot]='\0';
//	printf("cur_c:");
//	for(int i=tot-1;i>=0;i--) printf("%c",c[i]);
//	printf("\n");
}
void solve(int m1,int m2)
{
	while(s[m1]=='0'&&s[m2]=='0'){
		m1--;m2++;
	}
//	printf("m1:%d m2:%d\n",m1,m2);
	if(s[m1]=='0')
		cal(c,m2);
	else if(s[m2]=='0')
		cal(c,m1);
	else{
		cal(c,m1);
		cal(c2,m2);
		cal2(c,c2);
	}
}
int main()
{
	int m,m1,m2;
	while(~scanf("%d",&n)){
		scanf("%s",s);
		m=n/2;
		if(n%2==0){
			if(s[m]=='0'){
				m1=m;
				m2=m;
				solve(m1,m2);
			}else{
				cal(c,m);
			}
		}else{
			m1=m;m2=m+1;
			solve(m1,m2);
		}
		int len=strlen(c);
		for(int i=len-1;i>=0;i--) printf("%c",c[i]);
		printf("\n");
	}
	return 0;
}

C Flag

题意：给一个含nm个点的图，每个图最多有26个类型，分别为a-z;一个子图为flag图，如果该图由上中下三部分的类型点组成，三种类型两两互不相同，且其高度都相同，求一个nm的图，有多少个flag子图。 题解：st表，求原图s[][]的后缀之和suf[][]，然后对于每一列的累积suf值，我们用st表，查询每一列最小值，对应每个从当前列开始，行标为[l,r]时flag图有多少个。为了方便，把矩阵转置来处理。详见代码。 参考思路来自 xyq0220

#include
using namespace std;
#define ll long long
const int maxn=1010;

char s[maxn][maxn];
int suf[maxn][maxn];
int st[maxn][maxn][20];
int n,m;
void init()
{
	for(int i=1;i