2.4万

Tkybk_dz

2019-11-13 13:29
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;
const int N=50010;

int L,n,m;
int d[N];

bool check(int mid)
{
int last=0,cnt=0;
for(int i=1;i<=n;++i)
if(d[i]-last<mid) cnt++;
else last=d[i];
return cnt<=m;
}

int main(void)
{
scanf("%d%d%d",&L,&n,&m);
for(int i=1;i<=n;++i) scanf("%d",&d[i]);
d[++n]=L;
int l=1,r=1e9;
while(l<r)
{
int mid=l+r+1>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
printf("%d\n",r);
return 0;
}

2019-11-12 23:45
#include<bits/stdc++.h>
using namespace std;
int T,n,card[16],ans;

{
int x=0; char c=getchar();
while(c>'9'||c<'0') c=getchar();
while(c>='0'&&c<='9')
{
x=(x<<3)+(x<<1)+c-'0';
c=getchar();
}
return x;
}

inline void init()
{
memset(card,0,sizeof(card));
ans=n;
return ;
}

inline void dfs(int step,int point,int out)
{
if(step>=ans) return ;
if(out==n)  //出完所有的牌了
{
ans=step;
//cout<<step<<" "<<point<<" "<<out<<endl;
return;
}
if(point==16) return;
if(card[point]==0) dfs(step,point+1,out);
if(card[14]&&card[15])      //炸弹
{
card[14]--; card[15]--;
dfs(step+1,point,out+2);
card[14]++; card[15]++;
}
if(card[point]>=4)
{
card[point]-=4;
for(int i=1;i<=13;++i)  //四带二
{
if(card[i])
{
card[i]--;
for(int j=i;j<=15;++j)
{
if(card[j])
{
card[j]--;
dfs(step+1,point,out+6);
card[j]++;
}
}
card[i]++;
}
}
for(int i=1;i<=13;++i)
{
if(card[i]>=2)
{
card[i]-=2;
for(int j=i;j<=13;++j)
{
if(card[j]>=2)
{
card[j]-=2;
dfs(step+1,point,out+8);
card[j]+=2;
}
}
card[i]+=2;
}
}
card[point]+=4;
}
if(card[point]>=3)
{
card[point]-=3;
for(int i=point+1;i<=12;++i)    //三顺子
{
if(card[i]<3) break;
if(i-point+1>=2)
{
for(int j=point+1;j<=i;++j) card[j]-=3;
dfs(step+1,point,out+(i-point+1)*3);
for(int j=point+1;j<=i;++j) card[j]+=3;
}
}
for(int i=1;i<=15;++i)
{
if(i==point) continue;
if(card[i]>=1)              //三带一
{
card[i]--;
dfs(step+1,point,out+4);
card[i]++;
}
}
for(int i=1;i<=15;++i)
{
if(i==point) continue;
if(card[i]>=2)              //三带二
{
card[i]-=2;
dfs(step+1,point,out+5);
card[i]+=2;
}
}
dfs(step+1,point,out+3);        //三张牌
card[point]+=3;
}
if(card[point]>=2)
{
card[point]-=2;
for(int i=point+1;i<=12;++i)    //双顺子
{
if(card[i]<2) break;
if(i-point+1>=3)
{
for(int j=point+1;j<=i;++j) card[j]-=2;
dfs(step+1,point,out+(i-point+1)*2);
for(int j=point+1;j<=i;++j) card[j]+=2;
}
}
for(int i=1;i<=13;++i)  //对带四再带对
{
if(card[i]>=4)
{
card[i]-=4;
for(int j=1;j<=13;++j)
{
if(card[j]>=2&&j!=point)
{
card[j]-=2;
dfs(step+1,point,out+8);
card[j]+=2;
}
}
card[i]+=4;
}
}
for(int i=1;i<=13;++i)  //二带三
{
if(card[i]>=3&&i!=point)
{
card[i]-=3;
dfs(step+1,point,out+5);
card[i]+=3;
}
}
dfs(step+1,point,out+2);        //对子
card[point]+=2;
}
if(card[point])
{
card[point]--;
for(int i=point+1;i<=12;++i)    //单顺子
{
if(!card[i]) break;
if(i-point+1>=5)
{
for(int j=point+1;j<=i;++j) card[j]--;
dfs(step+1,point,out+i-point+1);
for(int j=point+1;j<=i;++j) card[j]++;
}
}
for(int i=1;i<=13;++i)  //单带四再带单
{
if(card[i]>=4)
{
card[i]-=4;
for(int j=1;j<=15;++j)
{
if(card[j])
{
card[j]--;
dfs(step+1,point,out+6);
card[j]++;
}
}
card[i]+=4;
}
}
for(int i=1;i<=13;++i)  //一带三
{
if(card[i]>=3&&i!=point)
{
card[i]-=3;
dfs(step+1,point,out+4);
card[i]+=3;
}
}
dfs(step+1,point,out+1);        //单牌
card[point]++;
}
return ;
}

int main(void)
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
while(T--)
{
init(); int a,b;
for(int i=1;i<=n;++i)
{
if(a==0){a=((b==1)?14:15);}
else if(a==1) a=12;
else if(a==2) a=13;
else a-=2; card[a]++;
}
//for(int i=1;i<=15;++i) cout<<card[i]<<endl;
dfs(0,1,0);
printf("%d\n",ans);
}
return 0;
}

2019-11-12 23:44
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 200010
using namespace std;
int fa[MAXN],deep[MAXN],n,ans=1e9;

inline int find(int x)
{
if(fa[x]!=x)
{
int last=fa[x];
fa[x]=find(fa[x]);
deep[x]+=deep[last];
}
return fa[x];
}

inline void check(int a,int b)
{
int x=find(a),y=find(b);
if(x!=y) {fa[x]=y; deep[a]=deep[b]+1;}
else ans=min(ans,deep[a]+deep[b]+1);
return;
}

int main(void)
{
scanf("%d",&n); int x;
for(int i=1;i<=n;++i) fa[i]=i;
for(int i=1;i<=n;++i)
{
scanf("%d",&x);
check(i,x);
}
printf("%d\n",ans);
return 0;
}

2019-11-12 10:24
#include<cstdio>
#include<iostream>
using namespace std;
const int N = 40;
int n,ans[N][N];

int main(void)
{
scanf("%d",&n);
ans[1][n/2+1]=1;
int lx=1,ly=n/2+1;
for(int i=2;i<=n*n;++i)
{
if(lx==1&&ly!=n) lx=n,ly=ly+1;
else if(lx!=1&&ly==n) lx=lx-1,ly=1;
else if(lx==1&&ly==n) lx=lx+1,ly=n;
else
{
if(!ans[lx-1][ly+1]) lx=lx-1,ly=ly+1;
else lx=lx+1,ly=ly;
}
ans[lx][ly]=i;
}
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
printf("%d ",ans[i][j]);
printf("\n");
}
return 0;
}

2019-11-12 09:23
#include<bits/stdc++.h>
#define MAXN 105
#define MAXM 1000010
using namespace std;
typedef long long ll;
const int mod=1000000009;
int n,m,A[MAXN],ans[MAXM],sum,cnt;
bool flag=1;

{
int x=0,f=1; char c=getchar();
while(c>'9'||c<'0')
{
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
x=(x*1ll*10+c-'0')%mod;
c=getchar();
}
return x*f;
}

inline void write(int x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
return ;
}

inline bool check(int x)
{
int res=A[n];
for(int i=n-1;i>=0;--i)
res=(res*1ll*x+A[i])%mod;
return !res;
}

int main(void)
{
//freopen("in.txt","r",stdin);
for(int i=1;i<=m;++i)
if(check(i))
{
sum++; ans[++cnt]=i;
}
write(sum); printf("\n");
for(int i=1;i<=cnt;++i)
{
write(ans[i]);
printf("\n");
}
return 0;
}

2019-11-12 09:11
#include<bits/stdc++.h>
#define rint register int
#define MAXN 100010
#define MAXM 200020
using namespace std;
bool vis1[MAXN],vis2[MAXN],book[MAXN];
const int inf=1000000;

struct Edge
{
int v,w,next;
}edge[MAXM],cedge[MAXM];

struct NODE
{
int u,d;
bool operator <(const NODE& rhs) const {
return d>rhs.d;
}
};

{
register char c=getchar(); rint x=0; short f=1;
while(c>'9'||c<'0')
{
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
x=(x<<3)+(x<<1)+c-'0';
c=getchar();
}
return x*f;
}

inline void add(int u,int v)
{
edge[++cnt].v=v;
return ;
}

inline void cadd(int u,int v)
{
cedge[++ccnt].v=v;
return ;
}

inline void dfs1(int x)
{
vis1[x]=true;
{
int v=cedge[i].v;
if(vis1[v]) continue;
dfs1(v);
}
return ;
}

inline void dfs2(int x)
{
vis2[x]=true;
{
int v=edge[i].v;
if(!vis1[v]) book[x]=true;
if(vis2[v]) continue;
dfs2(v);
}
return ;
}

inline void Dijkstra()
{
fill(dis+1,dis+n+1,inf);
dis[start]=0;
priority_queue<NODE> Q;
Q.push((NODE){start,0});
while(!Q.empty())
{
NODE fr=Q.top(); Q.pop();
int u=fr.u,d=fr.d;
if(d!=dis[u]) continue;
{
int v=edge[i].v,w=1;
if(book[v]) continue;
if(dis[u]+w<dis[v])
{
dis[v]=dis[u]+w;
Q.push((NODE){v,dis[v]});
}
}
}
return ;
}

int main(void)
{
//freopen("in.txt","r",stdin);
int a,b;
for(int i=1;i<=m;++i)
{
}
dfs1(endd); dfs2(start);
Dijkstra();
if(dis[endd]==inf) printf("-1");
else printf("%d",dis[endd]);
return 0;
}

2019-11-12 09:09
#include<iostream>
#include<cstdio>
using namespace std;
int n,d,sum[180][180],ans,cnt;

int main(void)
{
//freopen("in.txt","r",stdin);
scanf("%d%d",&d,&n); int x,y,z;
for(int i=1;i<=n;++i)
{
scanf("%d%d%d",&x,&y,&z);
sum[x+21][y+21]=z;
}
for(int i=1;i<=169;++i)
for(int j=1;j<=169;++j)
sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
for(int i=21;i<=149;++i)
for(int j=21;j<=149;++j)
{
int res=sum[i+d][j+d]-sum[i-d-1][j+d]-sum[i+d][j-d-1]+sum[i-d-1][j-d-1];
if(res>ans){ ans=res; cnt=1;}
else if(res==ans) cnt++;
}
printf("%d %d\n",cnt,ans);
return 0;
}

2019-11-12 08:44
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define MAXN 10010
#define MAXM 2010
using namespace std;
const int inf=0x3f3f3f3f;
int n,m,p,up[MAXN],down[MAXN],ans,f[MAXN][MAXM],low[MAXN],high[MAXN];
bool book[MAXN];    //标记位置i有没有管道
//f[i][j]表示到达（i,j）的最小点击次数

int main(void)
{
//freopen("in.txt","r",stdin);
scanf("%d%d%d",&n,&m,&p); int x,y,z;
for(int i=1;i<=n;++i) scanf("%d%d",&up[i],&down[i]);
for(int i=1;i<=n;++i){low[i]=1; high[i]=m;}
for(int i=1;i<=p;++i)
{
scanf("%d%d%d",&x,&y,&z);
book[x]=1;
low[x]=y+1; high[x]=z-1;
}
memset(f,0x3f,sizeof(f));
for(int i=1;i<=m;++i) f[0][i]=0;
for(int i=1;i<=n;++i)
{
for(int j=up[i]+1;j<=m+up[i];++j)
f[i][j]=min(f[i-1][j-up[i]]+1,f[i][j-up[i]]+1);
for(int j=m+1;j<=m+up[i];++j)   //超过m不会死，而是不会接着上升。
f[i][m]=min(f[i][m],f[i][j]);
for(int j=1;j<=m-down[i];++j)
f[i][j]=min(f[i][j],f[i-1][j+down[i]]);
for(int j=1;j<low[i];++j) f[i][j]=inf;   //不能通过(INF)
for(int j=high[i]+1;j<=m;++j) f[i][j]=inf;   //不能通过(INF)
}
ans=0x3f3f3f3f;
for(int i=1;i<=m;++i) ans=min(ans,f[n][i]);
if(ans<inf)
{
puts("1");
printf("%d\n",ans);
}
else
{
int i,j;
for(i=n;i>=1;--i) //从后向前遍历
{
for(j=1;j<=m;++j)
if(f[i][j]<inf) break; //如果能到达
if(j<=m) break;
}
ans=0;
for(int j=1;j<=i;++j)
if(book[j]) ans++;
puts("0");
printf("%d\n",ans);
}
return 0;
}

2019-11-12 08:04
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 200010
using namespace std;
const int mod = 10007;
int n,val[MAXN],ans1,ans2;

inline void add(int u,int v)
{
to[++cnt]=v;
return ;
}

int main(void)
{
//freopen("in.txt","r",stdin);
scanf("%d",&n); int x,y;
for(int i=1;i<=n-1;++i)
{
scanf("%d%d",&x,&y);
}
for(int i=1;i<=n;++i) scanf("%d",&val[i]);
for(int i=1;i<=n;++i)
{
int max1=0,max2=0;  //最大的两个权值
int t1=0,t2=0;      //t1代表和的平方，t2代表平方和
{
int v=to[j];
if(val[v]>max1) max2=max1,max1=val[v];
else if(val[v]>max2) max2=val[v];
t1=(t1+val[v])%10007;
t2=(t2+val[v]*val[v])%10007;
}
t1=t1*t1%10007;
ans2=(ans2+t1+10007-t2)%10007;
if(ans1<max1*max2) ans1=max1*max2;
}
printf("%d %d\n",ans1,ans2);
return 0;
}

2019-11-12 07:32
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 210;
int n,na,nb,a[N],b[N],cnta,cntb;
int vs[5][5] = {{0,0,1,1,0},{1,0,0,1,0},{0,1,0,0,1},{0,0,1,0,1},{1,1,0,0,0}};

int main(void)
{
scanf("%d%d%d",&n,&na,&nb);
for(int i=0;i<na;++i) scanf("%d",&a[i]);
for(int i=0;i<nb;++i) scanf("%d",&b[i]);
for(int i=0;i<n;++i)
{
cnta+=vs[a[i%na]][b[i%nb]];
cntb+=vs[b[i%nb]][a[i%na]];
}
printf("%d %d\n",cnta,cntb);
return 0;
}