849A - Odds and Ends

问能否将序列划分为奇数个长度奇数的奇数开头奇数结尾的子区间。

一开始想dp。。不过没必要。

const int N=201000;

int n,a[N];

int main() {

	sf(n);

	rep(i,1,n+1)sf(a[i]);

	bool ans=1;

	if(a[1]%2==0||a[n]%2==0||n%2==0){

		ans=0;

	}

	puts(ans?"Yes":"No");

	return 0;

}

849B - Tell Your World

n个点坐标为\((i,y_i)\)，问是否有两条不重合的平行线，点都在上面，且一条线至少一个点。

找到和第1，2个点不共线的点b，然后枚举这三条边作为平行线的一条，其它点就必须在线上或者和另一个点连线和这条线平行。

我sb了把b点和第3个点swap了一下（哭）。代码写得有点长。。

const int N=201000;

int n,y[N];

double k;

int main() {

	sf(n);

	rep(i,0,n)sf(y[i]);

	int b=-1;

	rep(i,2,n)if((ll)(y[i]-y[0])*(i-1)!=(ll)(y[i]-y[1])*i){

		b=i;break;

	}

	if(~b){

		bool ans=0,tans=1;

		rep(i,2,n)if(i!=b){

			bool t=(ll)(y[i]-y[0])*(i-1)!=(ll)(y[i]-y[1])*i;

			bool s=(ll)(y[i]-y[b])!=(ll)(y[1]-y[0])*(i-b);

			if(s && t){

				tans=0;break;

			}

		}

		ans|=tans;

		tans=1;

		rep(i,2,n)if(i!=b){

			bool t=(ll)(y[i]-y[0])*(i-b)!=(ll)(y[i]-y[b])*i;

			bool s=(ll)(y[i]-y[1])*b!=(ll)(y[b]-y[0])*(i-1);

			if(s && t){

				tans=0;break;

			}

		}

		ans|=tans;

		tans=1;

		rep(i,2,n)if(i!=b){

			bool t=(ll)(y[i]-y[1])*(i-b)!=(ll)(y[i]-y[b])*(i-1);

			bool s=(ll)(y[i]-y[0])*(b-1)!=(ll)(y[b]-y[1])*i;

			if(s && t){

				tans=0;break;

			}

		}

		ans|=tans;

		puts(ans?"Yes":"No");

	}else {

		puts("No");

	}

	return 0;

}

849C - From Y to Y

给你一个k，求一个字符串，要求组成的费用为k。

费用：两个字符串拼起来，代价为每个字母在两个串中的个数之积求和，一开始是n个字母，拼n-1次可以成为一个长度n的字符串。

不同字母的计算是独立的，相同的两个字母在两个不同串里乘起来时贡献了1，所以有\(num_i\)个i字母就有\(C(num_i,2)\)次贡献。

k最大100000，每次贪心找贡献不超过k的最大的num，5个字母都足够了。

我漏了0的情况又wa一次→_→

const int N=1000;

int pre[N];

int n;

char s[N*N];

int len;

int main() {

	rep(i,0,N)pre[i]=(i-1)*i/2;

	sf(n);

	if(n==0)puts("a");

	int j,c;

	while(n>0){

		j=lower_bound(pre, pre+N, n)-pre;

		if(pre[j]>n)--j;

		n-=pre[j];

		rep(i,0,j)s[len++]='a'+c;

		++c;

	}

	printf("%s",s);

	return 0;

}