Diary of March 21st

3
21
2016

上午打了VK CUP 2016资格赛第二场……

因为第一场D题FST了所以没进前500所以还要打一场

感觉智商太低了

B题问R爷 R爷说我题目看错了

C题问阳神阳神瞬间秒掉了

D题问比利比利也秒掉了……

感觉自己真是弱到一种境界了

PS: 后面几天省选先暂停几天

Codeforces638A

SB题不解释

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
using namespace std;
inline ll IN(){
	ll x=0;int ch=getchar(),f=1;
	while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
	if (ch=='-'){f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
inline void OUT(ll x){
	if (x<0) putchar('-'),x=-x;
	if (x>=10) OUT(x/10),putchar(x%10+'0');
		else putchar(x+'0');
}
int main(){
	int n=IN(),a=IN();
	if (a&1) printf("%d\n",(a+1)/2);
	else printf("%d\n",(n-a)/2+1);
}

Codeforces638B

读入的串能确定这个串中的字符的相邻关系

记录一下每个字母的后继以后直接输出就可以了

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
using namespace std;
inline ll IN(){
	ll x=0;int ch=getchar(),f=1;
	while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
	if (ch=='-'){f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
inline void OUT(ll x){
	if (x<0) putchar('-'),x=-x;
	if (x>=10) OUT(x/10),putchar(x%10+'0');
		else putchar(x+'0');
}
int n,suf[30];
void DFS(int u){
	putchar(u+'a');
	if (~suf[u]) DFS(suf[u]);
}
bool vis[30],in[30];
char s[30];
int main(){
	n=IN();
	memset(suf,-1,sizeof suf);
	Rep(i,1,n){
		scanf("%s",s);
		int len=strlen(s);
		vis[s[0]-'a']=1;
		Rep(j,0,len-2){
			suf[s[j]-'a']=s[j+1]-'a';
			vis[s[j+1]-'a']=in[s[j+1]-'a']=1;
		}
	}
	Rep(i,0,25) if (vis[i]&&!in[i]) DFS(i);
}

Codeforces638C

DFS 记录一下连着这个点的那条边是第几天做的

然后把它的每棵子树的根依次赋成 $1,2,3..$

赋值的时候如果和父亲是一样的天数就跳过这天就可以了

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
using namespace std;
inline ll IN(){
	ll x=0;int ch=getchar(),f=1;
	while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
	if (ch=='-'){f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
inline void OUT(ll x){
	if (x<0) putchar('-'),x=-x;
	if (x>=10) OUT(x/10),putchar(x%10+'0');
		else putchar(x+'0');
}
const int N=200005;
vector<int>Ans[N];
int k,n,cnt,to[N*2],next[N*2],id[N*2],head[N];
void AddEdge(int u,int v,int idx){
	to[cnt]=v;next[cnt]=head[u];id[cnt]=idx;head[u]=cnt++;
}
int Mx;
void DFS(int u,int fa,int d){
	int now=0;
	Cross(i,u){
		if (to[i]!=fa){
			now++;if (now==d) now++;
			Mx=max(Mx,now);
			Ans[now].push_back(id[i]);
			DFS(to[i],u,now);
		}
	}
}
int main(){
	n=IN();
	memset(head,-1,sizeof head);
	Rep(i,1,n-1){
		int u=IN(),v=IN();
		AddEdge(u,v,i);
		AddEdge(v,u,i);
	}
	DFS(1,0,0);
	OUT(Mx),putchar('\n');
	Rep(i,1,Mx){
		OUT(Ans[i].size()),putchar(' ');
		Rep(j,0,Ans[i].size()-1)
			OUT(Ans[i][j]),putchar(' ');
		putchar('\n');
	}
}

Codeforces638D

考虑每个点

如果它的每个前驱都能不通过它到达它的每个后继

那这个点一定不是重要点，否则一定是

特判一下就可以了

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
using namespace std;
inline ll IN(){
	ll x=0;int ch=getchar(),f=1;
	while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
	if (ch=='-'){f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
inline void OUT(ll x){
	if (x<0) putchar('-'),x=-x;
	if (x>=10) OUT(x/10),putchar(x%10+'0');
		else putchar(x+'0');
}
const int N=105;
char s[N][N][N];
int n,m,p,Ans;
int main(){
	n=IN(),m=IN(),p=IN();
	Rep(i,1,n) Rep(j,1,m) scanf("%s",s[i][j]+1);
	Rep(i,1,n) Rep(j,1,m) Rep(k,1,p){
		if (s[i][j][k]=='0') continue;
		bool f=0;
		if (i!=1&&s[i-1][j][k]=='1'){
			if (i!=n&&s[i+1][j][k]=='1') f=1;
			if (j!=m&&s[i][j+1][k]=='1'&&s[i-1][j+1][k]=='0') f=1;
			if (k!=p&&s[i][j][k+1]=='1'&&s[i-1][j][k+1]=='0') f=1; 
		}
		if (j!=1&&s[i][j-1][k]=='1'){
			if (i!=n&&s[i+1][j][k]=='1'&&s[i+1][j-1][k]=='0') f=1;
			if (j!=m&&s[i][j+1][k]=='1') f=1;
			if (k!=p&&s[i][j][k+1]=='1'&&s[i][j-1][k+1]=='0') f=1;
		}
		if (k!=1&&s[i][j][k-1]=='1'){
			if (i!=n&&s[i+1][j][k]=='1'&&s[i+1][j][k-1]=='0') f=1;
			if (j!=m&&s[i][j+1][k]=='1'&&s[i][j+1][k-1]=='0') f=1;
			if (k!=p&&s[i][j][k+1]=='1') f=1;
		}
		if (f) Ans++;
	}
	OUT(Ans);
}

BZOJ1010

斜率优化DP

惯例先写一个 $N^2$ 的DP

$f_i=min\{f_j+(i-j+pre_i-pre_j-(L+1))^2\}$

设 $g_i=i+pre_i$，那么

$f_i=min\{f_j+(g_i-g_j-(L+1))^2$

$f_i=min\{f_j-2g_ig_j+(g_j+(L+1))^2\}+(g_i-(L+1))^2$

假设 $k<j$ 那么 $j$ 比 $k$ 优的条件是

$\frac{f_j+(g_j+(L+1))^2-f_k-(g_k+(L+1))^2}{2(g_j-g_k)}\le f_i$

然后就可以用队列维护了

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
using namespace std;
inline ll IN(){
	ll x=0;int ch=getchar(),f=1;
	while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
	if (ch=='-'){f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
inline void OUT(ll x){
	if (x<0) putchar('-'),x=-x;
	if (x>=10) OUT(x/10),putchar(x%10+'0');
		else putchar(x+'0');
}
const int N=50005;
ll g[N],f[N];
int n,L,h,t,q[N];
ll sqr(ll a){return a*a;}
double Y(int i,int j){
	return 1.0*(f[j]+sqr(g[j])-f[i]-sqr(g[i])+2*(L+1)*(g[j]-g[i]));
}
double X(int i,int j){
	return 2.0*(g[j]-g[i]);
}
int main(){
	n=IN(),L=IN();
	g[0]=0;Rep(i,1,n) g[i]=g[i-1]+IN()+1;
	f[0]=0; 
	h=t=1;q[t]=0;
	Rep(i,1,n){
		while (h<t&&Y(q[h],q[h+1])/X(q[h],q[h+1])<g[i]) h++;
		f[i]=g[i]*-2*g[q[h]]+f[q[h]]+sqr(g[q[h]])+2*(L+1)*g[q[h]]+sqr(g[i]-L-1);
		while (t>h&&Y(q[t],i)/X(q[t],i)<Y(q[t-1],q[t])/X(q[t-1],q[t])) t--;
		q[++t]=i;
	}
	OUT(f[n]);
}

Category: Diary | Tags: DP 凸包搜索 SB题特判 | Read Count: 789

[回复]

AP SSC Urdu Model Pa 说:
Sep 19, 2022 01:10:20 AM

Urdu is one of the main languages in the state, and this is the first language for Urdu Medium students, there are fewer schools are working in all districts of the state, all the applicable students also can download AP SSC Urdu Model Paper 2023 Pdf in chapter wise for all lessons of the course, AP SSC Urdu Model Paper download, and practice the Ibtedai Question bank to get better rank in all exams conducted by BSEAP. Urdu is one of the main languages in the state, and this is the first language for Urdu Medium students, there are fewer schools are working in all districts of the state, all the applicable students also can download AP SSC Urdu Model Paper 2023 Pdf in chapter wise for all lessons of the course.

WTRC's Memory

三世烟火沧笙踏歌