RT，发现找不到题，于是又开了新坑
JOI特色：重思考，代码难度(相比NOI系列)基本没有
(省选前到处挖坑2333)
JOI 2017 Final
焚风现象
差分，莫得了
(不是看到200ms就tm线段树去了
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
long long ans,dif[N];
int n,m,s,t,t1,t2,t3,rd,lst;
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&t);
scanf("%d",&rd);
for(int i=;i<=n;i++)
{
scanf("%d",&rd);
dif[i]=rd-lst,lst=rd;
ans-=(dif[i]>)?(1ll*s*dif[i]):(1ll*t*dif[i]);
}
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&t1,&t2,&t3);
ans+=(dif[t1]>)?(1ll*s*dif[t1]):(1ll*t*dif[t1]);
dif[t1]+=t3;
ans-=(dif[t1]>)?(1ll*s*dif[t1]):(1ll*t*dif[t1]);
if(t2!=n)
{
t2++;
ans+=(dif[t2]>)?(1ll*s*dif[t2]):(1ll*t*dif[t2]);
dif[t2]-=t3;
ans-=(dif[t2]>)?(1ll*s*dif[t2]):(1ll*t*dif[t2]);
}
printf("%lld\n",ans);
}
return ;
}
准高速电车
观察性质以进行贪心
题意可能有那么一点糊，其实是你可以走多次然后求和，只要每次都不超过T即可
注意题目保证速度按常识给出
我们发现一次出行一定是先坐快车，然后换乘准快车，最后坐慢车。而且显然我们最后一次一定是从一个快车站开始然后到不了下一个快车站的，所以我们只要考虑两两相邻的快车站中间即可
那我们就先只考虑一对相邻的快车站且我们在中间结束的情况，我们现在要在中间放一些准快车站，而我们选择在哪个准快车站结束相当于在后面一段用剩下的时间对右侧进行了一个覆盖，且这个覆盖的长度单调不升(显然越到后面剩的时间越少)。同样显然的是覆盖不会相交(否则不优)且一个覆盖的结束与下一个准快车站(如果还有的话)是相邻的(否则也不优)。于是问题变成了贪心，用堆维护每对相邻的快车站里准快车站覆盖的区间即可，记录剩余时间，剩余车站数和覆盖的长度，贪心选覆盖长度前k大的并每次更新
注意如果用高速能跑完相当于最后一个闭合了，答案+1
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lli long long
using namespace std;
const int N=;
struct node
{
lli tim;
int len,mxl;
};
bool operator < (node x,node y)
{
return x.len<y.len;
}
int n,m,k,a,b,c,ans,s[N];
lli T; priority_queue<node> hp;
void Insert(lli t,int l,int k)
{
if(t<||l<) return;
int cov=min(t/a,(lli)l)+;
if(k) ans+=cov,Insert(t-1ll*cov*c,l-cov,);
else hp.push((node){t,cov,l});
}
int main()
{
scanf("%d%d%d",&n,&m,&k),k-=m;
scanf("%d%d%d%lld",&a,&b,&c,&T);
for(int i=;i<=m;i++) scanf("%d",&s[i]);
for(int i=;i<m;i++) Insert(T-1ll*(s[i]-)*b,s[i+]-s[i]-,);
while(!hp.empty()&&k--)
{
node tn=hp.top(); hp.pop();
Insert(tn.tim,tn.mxl,);
}
printf("%d",ans-+(1ll*(s[m]-)*b<=T));
return ;
}
JOIOI王国
这种东西肯定是二分加检验，考虑怎么检验
我们发现割开最大值和最小值一定是最优的，那么我们四个方向都搞一搞，逐行找分界线即可
注意如果要满足限制4最后一定切出来是一个阶梯形(没想这个调了半天。。。)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=,inf=1e9;
int n,m,mx,mn,rd,ans,s[][N][N];
bool Check(int t,int x)
{
int up=mx-x,dw=mn+x,b=m;
for(int i=;i<=n;i++)
{
for(int j=;j<=b;j++)
if(s[t][i][j]<up) {b=j-;break;}
for(int j=b+;j<=m;j++)
if(s[t][i][j]>dw) return false;
}
return true;
}
int Calc(int idx)
{
int l=mn,r=mx,ret=r;
while(l<=r)
{
int mid=(l+r)>>;
if(Check(idx,mid)) r=mid-,ret=mid;
else l=mid+;
}
return ret;
}
int main()
{
scanf("%d%d",&n,&m),mn=ans=inf;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
scanf("%d",&rd),mx=max(mx,rd),mn=min(mn,rd);
s[][i][j]=s[][j][n-i+]=s[][n-i+][m-j+]=s[][m-j+][i]=rd;
}
ans=min(ans,Calc()); swap(n,m);
ans=min(ans,Calc()); swap(n,m);
ans=min(ans,Calc()); swap(n,m);
ans=min(ans,Calc()); swap(n,m);
printf("%d",ans);
return ;
}
足球
首先把题目抽象成最短路问题，然后发现直接建图边数爆炸了
优化是我们把每个位置拆点，分成“球员在控球”和“球正在向某个方向飞”这五个点，BFS预处理一下到某个点接住球的最小代价，然后就没了
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lli long long
using namespace std;
const int N=,M=,K=;
const int mov[][]={{,},{-,},{,},{,-}};
struct s{int node;lli dist;};
bool operator < (s x,s y)
{
return x.dist>y.dist;
}
priority_queue<s> hp;
pair<int,int> que[N]; lli val[M],dis[N];
int n,m,k,a,b,c,t1,t2,st,ed,hd,tl,cnt,tot;
int stp[K][K],idx[K][K],vis[N],p[N],noww[M],goal[M];
bool Check(int x,int y)
{
return x>=&&y>=&&x<=n&&y<=m;
}
void Link(int f,int t,lli v)
{
noww[++cnt]=p[f],p[f]=cnt;
goal[cnt]=t,val[cnt]=v;
}
void Dijkstra(int st)
{
memset(dis,0x3f,sizeof dis);
dis[st]=,hp.push((s){st,});
while(!hp.empty())
{
s t=hp.top(); hp.pop(); int tn=t.node;
if(vis[tn]) continue; vis[tn]=true;
for(int i=p[tn],g;i;i=noww[i])
if(dis[g=goal[i]]>dis[tn]+val[i])
dis[g]=dis[tn]+val[i],hp.push((s){g,dis[g]});
}
}
int main()
{
register int i,j,h;
scanf("%d%d%d%d%d%d",&n,&m,&a,&b,&c,&k),tot=;
for(i=;i<=n;i++)
for(j=;j<=m;j++) idx[i][j]=tot,tot+=;
hd=,tl=-,memset(stp,-,sizeof stp);
for(i=;i<=k;i++)
{
scanf("%d%d",&t1,&t2);
stp[t1][t2]=,que[++tl]=make_pair(t1,t2);
if(i==) st=idx[t1][t2]; if(i==k) ed=idx[t1][t2];
}
while(hd<=tl)
{
pair<int,int> pr=que[hd++];
for(i=;i<;i++)
{
int xx=pr.first,yy=pr.second;
int tx=xx+mov[i][],ty=yy+mov[i][];
if(Check(tx,ty)&&stp[tx][ty]==-)
{
stp[tx][ty]=stp[xx][yy]+;
que[++tl]=make_pair(tx,ty);
}
}
}
for(i=;i<=n;i++)
for(j=;j<=m;j++)
{
int nde=idx[i][j];
for(h=;h<;h++)
{
Link(nde+h+,nde,1ll*stp[i][j]*c);
int tx=i+mov[h][],ty=j+mov[h][];
if(Check(tx,ty))
{
Link(nde,idx[tx][ty],c);
Link(nde+h+,idx[tx][ty]+h+,a);
Link(nde,idx[tx][ty]+h+,a+b);
}
}
}
Dijkstra(st); long long ans=1e18;
for(i=;i<=;i++) ans=min(ans,dis[ed+i]);
printf("%lld",ans);
return ;
}
绳
首先观察到一开始先染好色再折叠和边折叠边染色是一样的
先给出结论：对于每个颜色，我们令奇数根绳子分别尝试和左边或右边的绳子配对，然后统计颜色的众数，答案即 总数-当前颜色的绳数-众数，两种方式取min即是答案
方案最优的正确性显然(最后保留的就是当前颜色和众数)
方案存在的正确性是因为我们硬点最后剩下当前颜色和区间众数，就变成了一个01序列，于是没有对不上的情况了(注意这里说的一个0或者1是两个数合起来的)
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1e6+;
vector<int> ve[N];
int n,m,mx,col[N],bkt[N],app[N];
void Add(int c){--app[bkt[c]],++app[++bkt[c]]; mx=max(mx,bkt[c]);}
void Del(int c){--app[bkt[c]],++app[--bkt[c]]; if(!app[mx]) mx--;}
int Oth(int x){return (x&)?(x+):(x-);}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
{
scanf("%d",&col[i]);
ve[col[i]].push_back(i),Add(col[i]);
}
for(int i=;i<=m;i++)
{
col[]=col[n+]=i;
int tot=ve[i].size(),ans=n;
for(int j=;j<tot;j++) Del(i);
for(int j=;j<tot;j++)
if(col[Oth(ve[i][j])]!=i)
Del(col[Oth(ve[i][j])]);
ans=min(ans,n-tot-mx);
for(int j=;j<tot;j++)
{
if(col[Oth(ve[i][j])]!=i)
Add(col[Oth(ve[i][j])]);
if(col[ve[i][j]^]!=i)
Del(col[ve[i][j]^]);
}
ans=min(ans,n-tot-mx);
for(int j=;j<tot;j++)
if(col[ve[i][j]^]!=i)
Add(col[ve[i][j]^]);
for(int j=;j<tot;j++) Add(i);
printf("%d\n",ans);
}
return ;
}
JOI 2017 Final 完结撒花
JOI 2018 Final
寒冬暖炉
真实普及组题，贪心一下就莫得了
这题都WA两次，你说这人还怎么救啊
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
int n,k,rd,lst,cnt,ans,len[N];
int main()
{
scanf("%d%d%d",&n,&k,&lst),ans=n;
for(int i=;i<=n;i++)
{
scanf("%d",&rd);
if(lst+!=rd) len[++cnt]=rd-lst-; lst=rd;
}
sort(len+,len++cnt);
for(int i=;i<=cnt;i++) ans+=len[i];
for(int i=;i<k;i++) ans-=len[cnt-i+];
printf("%d",ans);
return ;
}
美术展览
真实普及题，拆式子然后扫一遍
感觉自己在颓普及组题，没救了
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
struct a{long long a,b;}o[N];
bool cmp(a x,a y)
{
return x.b<y.b;
}
long long n,t1,t2,mn,ans,s[N],x[N],y[N];
int main()
{
scanf("%lld",&n);
for(int i=;i<=n;i++)
scanf("%lld%lld",&t1,&t2),o[i]=(a){t2,t1};
sort(o+,o++n,cmp);
for(int i=;i<=n;i++)
{
s[i]=s[i-]+o[i].a;
x[i]=s[i-]-o[i].b,y[i]=s[i]-o[i].b;
}
ans=y[],mn=x[];
for(int i=;i<=n;i++)
mn=min(mn,x[i]),ans=max(ans,y[i]-mn);
printf("%lld",ans);
return ;
}
团子制作
奇怪的DP，注意题目要求有顺序而且必须是严格左到右和上到下(不然反正我不会做=。=)
沿着斜对角线DP，三位DP一个记横着的一个记竖着的一个当中间变量从上两个(当前格子横着插，上一个竖着插，这两个冲突所以要取一个优的)里取最优的
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
int n,m,x,y,ans,dp[];
char tuan[N][N];
bool oo1(int x,int y)
{
return tuan[x][y]=='R'&&tuan[x][y+]=='G'&&tuan[x][y+]=='W';
}
bool oo2(int x,int y)
{
return tuan[x][y]=='R'&&tuan[x+][y]=='G'&&tuan[x+][y]=='W';
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) scanf("%s",tuan[i]+);
for(int i=;i<=n+m-;i++)
{
i<=m?(x=,y=i):(x=i-m+,y=m);
memset(dp,,sizeof dp);
while(x<=n&&y>=)
{
dp[]=max(dp[],dp[]+oo1(x,y));
dp[]=max(dp[],dp[]);
dp[]=max(dp[],dp[]+oo2(x,y));
x++,y--;
}
ans+=dp[];
}
printf("%d",ans);
return ;
}
月票购买
把s到t最短路上的边提出来搞成零再跑u到v的最短路，然后发现自己想水了，显然这样可能会走两条路，不合法
但是可以部分借鉴这个思路，发现最后一定是先从u出发走一段，然后在选的最短路上走一段，最后再从最短路上离开走到t。于是预处理从四个点出发的最短路，从s开始一次DFS把路径拼起来。
数组玄学开小，最后只能无脑调大，wsl
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=;
struct a
{
int node;
long long dist;
};
bool operator < (a x,a y)
{
return x.dist>y.dist;
}
priority_queue<a> hp;
int n,m,u,v,w,s1,t1,s2,t2,cnt;
int p[M],noww[M],goal[M],vis[M];
long long val[M],mnu[M],mnv[M];
long long dis1[M],dis2[M],dis3[M],dis4[M];
void Link(int f,int t,int v)
{
noww[++cnt]=p[f],p[f]=cnt;
goal[cnt]=t,val[cnt]=v;
noww[++cnt]=p[t],p[t]=cnt;
goal[cnt]=f,val[cnt]=v;
}
void Dijkstra(int s,long long *dis)
{
memset(vis,,sizeof vis);
memset(dis,0x3f,sizeof vis);
dis[s]=,hp.push((a){s,});
while(!hp.empty())
{
a t=hp.top(); hp.pop(); int tn=t.node;
if(vis[tn]) continue; vis[tn]=true;
for(int i=p[tn],g;i;i=noww[i])
if(dis[g=goal[i]]>dis[tn]+val[i])
dis[g]=dis[tn]+val[i],hp.push((a){g,dis[g]});
}
}
void DFS(int nde)
{
vis[nde]=true,mnu[nde]=dis3[nde],mnv[nde]=dis4[nde];
for(int i=p[nde],g;i;i=noww[i])
if(dis1[nde]+dis2[g=goal[i]]+val[i]==dis1[t1])
{
if(!vis[g]) DFS(g);
if(mnu[nde]+mnv[nde]>min(dis3[nde],mnu[g])+min(dis4[nde],mnv[g]))
mnu[nde]=min(dis3[nde],mnu[g]),mnv[nde]=min(dis4[nde],mnv[g]);
}
}
int main()
{
scanf("%d%d",&n,&m),cnt=;
scanf("%d%d%d%d",&s1,&t1,&s2,&t2);
for(int i=;i<=m;i++)
scanf("%d%d%d",&u,&v,&w),Link(u,v,w);
Dijkstra(s1,dis1),Dijkstra(t1,dis2);
Dijkstra(s2,dis3),Dijkstra(t2,dis4);
memset(vis,,sizeof vis),DFS(s1);
printf("%lld",min(mnu[s1]+mnv[s1],dis3[t2]));
return ;
}
毒蛇越狱
事实证明逃课是早晚要补的
发现$min('1','0'',?')<=6$，在这上面做文章
首先'?'少的时候直接暴力枚举即可
考虑'0'少的时候，用超集和容斥
考虑‘1’少的时候，用子集和容斥
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=,M=(<<)+;
int n,q,all,sub[M],sup[M],sum[M],cnt[M]; char str[M];
int main()
{
scanf("%d%d%s",&n,&q,str),all=(<<n)-;
for(int i=;i<=all;i++)
sub[i]=sup[i]=sum[i]=str[i]-'',cnt[i]=cnt[i>>]+(i&);
for(int i=;i<n;i++)
for(int j=,k=<<i;j<=all;j++)
if(!(j&k)) sub[j|k]+=sub[j],sup[j]+=sup[j|k];
while(q--)
{
scanf("%s",str);
int s1=,s2=,s3=,ans=;
for(int i=,t;i<n;i++)
t=<<(n-i-),str[i]==''?(s1|=t):(str[i]==''?(s2|=t):(s3|=t));
if(cnt[s1]<=)
for(int i=s1;;i=(i-)&s1)
{ans+=(cnt[i]&)?-sup[i|s2]:sup[i|s2]; if(!i) break;}
else if(cnt[s2]<=)
for(int i=s2;;i=(i-)&s2)
{ans+=(cnt[i^s2]&)?-sub[i|s3]:sub[i|s3]; if(!i) break;}
else if(cnt[s3]<=)
for(int i=s3;;i=(i-)&s3)
{ans+=sum[i|s2]; if(!i) break;}
printf("%d\n",ans);
}
return ;
}
JOI 2018 Final 完结撒花
感觉到了一丝丝不对劲，是不是JOISC比JOI Final要难啊。。。。。。wsl