3
21
2016
0

Diary of March 21st

上午打了VK CUP 2016资格赛第二场……
因为第一场D题FST了 所以没进前500所以还要打一场
感觉智商太低了
B题问R爷 R爷说我题目看错了
C题问阳神 阳神瞬间秒掉了
D题问比利 比利也秒掉了……
感觉自己真是弱到一种境界了
PS: 后面几天省选 先暂停几天

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);
}
读入的串能确定这个串中的字符的相邻关系
记录一下每个字母的后继以后直接输出就可以了
#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);
} 
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');
	}
}
考虑每个点
如果它的每个前驱都能不通过它到达它的每个后继
那这个点一定不是重要点,否则一定是
特判一下就可以了
#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);
}
斜率优化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: 309

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com