[JOI 2016 Final]オレンジの出荷
\(f_i\) 表示 \(1\sim i\) 的都放完的最小代价，数据范围支持 \(O(nm)\) dp。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=2e4+10;
int n,m,a[N],f[N],k;
void solve(){
read(n),read(m),read(k);
memset(f,0x3f,sizeof(f));
f[0]=0;
for(int i=1;i<=n;i++){
read(a[i]);
int mx=a[i],mn=a[i];
for(int j=i-1;j>=max(i-m,0ll);j--){
f[i]=min(f[i],f[j]+(i-j)*(mx-mn)+k);
mx=max(mx,a[j]);
mn=min(mn,a[j]);
}
}
write_endl(f[n]);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
[JOI 2016 Final]スタンプラリー 2
分类讨论，加 J 直接放开头，加 I 直接放结尾，加 O 可以预处理出每个位置前面 J 和后面 I 的数量，计算出增加的贡献，容易得到最大贡献。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=1e5+10;
int n,ans,prej[N],sufi[N];
char s[N];
void solve(){
read(n);
for(int i=1;i<=n;i++){
s[i]=getchar();
while(s[i]!='J'&&s[i]!='O'&&s[i]!='I'){
s[i]=getchar();
}
prej[i]=prej[i-1]+(s[i]=='J');
}
for(int i=n;i;i--){
sufi[i]=sufi[i+1]+(s[i]=='I');
}
int cnti=0,cntoi=0,nowans=0;
for(int i=n;i;i--){
if(s[i]=='I'){
cnti++;
}
else if(s[i]=='O'){
cntoi+=cnti;
}
else{
nowans+=cntoi;
}
}
ans=max(ans,nowans+cntoi);
cnti=1,cntoi=0,nowans=0;
for(int i=n;i;i--){
if(s[i]=='I'){
cnti++;
}
else if(s[i]=='O'){
cntoi+=cnti;
}
else{
nowans+=cntoi;
}
}
ans=max(ans,nowans);
cnti=0,cntoi=0,nowans=0;
for(int i=n;i;i--){
if(s[i]=='I'){
cnti++;
}
else if(s[i]=='O'){
cntoi+=cnti;
}
else{
nowans+=cntoi;
}
}
for(int i=1;i<=n;i++){
ans=max(ans,nowans+prej[i]*sufi[i+1]);
}
write_endl(ans);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
鉄道運賃
有一个显而易见的结论：任意时刻，一条从起点到一个满意的城市的路不会经过一条升过价的路，所以涨价等价于将这条路断掉。
断边不好处理，考虑反过来，断边转加边。但是不能每加一条边都全图重做求最短路，需要找到影响的点有哪些，从加的边的端点开始更新，只有当更新后的最短路为原图中的最短路时，再继续更新，否则等更新的路为原图中的最短路时更新肯定不劣，每个点最多更新一回，复杂度 \(O(n\log m+n)\)。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=1e5+10,M=2e5+10;
int n,m,q,u[M],v[M],r[M],lim[M<<1],d[N][2],vis[N],ans[M],tot,head[N],cnt=1;
struct edge{
int v,nxt;
}e[M<<1];
void add(int u,int v){
e[++tot].v=v;
e[tot].nxt=head[u];
head[u]=tot;
}
void bfs(int id){
queue<int>q;
for(int i=1;i<=n;i++){
d[i][id]=inf;
vis[i]=0;
}
q.push(1);
d[1][id]=0;
vis[1]=1;
while(q.size()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(vis[v]||lim[i]){
continue;
}
vis[v]=1;
d[v][id]=d[u][id]+1;
q.push(v);
}
}
}
void change(int x,int y){
int Max=max(d[x][1],d[y][1]),Min=min(d[x][1],d[y][1]);
if(Max==Min||Max==Min+1){
return;
}
if(d[x][1]>d[y][1]){
swap(x,y);
}
d[y][1]=d[x][1]+1;
if(d[y][1]!=d[y][0]){
return;
}
queue<int>q;
q.push(y);
for(int i=1;i<=n;i++){
vis[i]=0;
}
while(!q.empty()){
int u=q.front();
q.pop();
cnt++;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(vis[v]||lim[i]||d[v][1]<=d[u][1]+1){
continue;
}
vis[v]=1;
d[v][1]=d[u][1]+1;
if(d[v][1]==d[v][0]){
q.push(v);
}
}
}
}
void solve(){
read(n),read(m),read(q);
for(int i=1;i<=m;i++){
read(u[i]),read(v[i]);
add(u[i],v[i]);
add(v[i],u[i]);
}
for(int i=1;i<=q;i++){
read(r[i]);
}
bfs(0);
for(int i=1;i<=q;i++){
lim[r[i]*2]=lim[r[i]*2-1]=1;
}
bfs(1);
for(int i=2;i<=n;i++){
if(d[i][0]==d[i][1]){
cnt++;
}
}
for(int i=q;i;i--){
ans[i]=n-cnt;
lim[r[i]*2-1]=lim[r[i]*2]=0;
int x=u[r[i]],y=v[r[i]];
change(x,y);
}
for(int i=1;i<=q;i++){
write_endl(ans[i]);
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
[JOI 2017 Final]フェーン現象
因为温度和高度差有关，对原数组做差分，在差分数组上所有的修改操作直接区间转单点了。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=2e5+10;
int n,q,s,t,a[N];
int val(int x){
if(x>0){
return x*t;
}
if(x<0){
return x*s;
}
return 0;
}
void solve(){
read(n),read(q),read(t),read(s);
t=-t,s=-s;
int ans=0;
read(a[0]);
for(int i=1;i<=n;i++){
read(a[i]);
}
for(int i=n;i;i--){
a[i]=a[i]-a[i-1];
ans+=val(a[i]);
}
while(q--){
int l,r,v;
read(l),read(r),read(v);
ans-=val(a[l]);
a[l]+=v;
ans+=val(a[l]);
if(r<n){
ans-=val(a[r+1]);
a[r+1]-=v;
ans+=val(a[r+1]);
}
write_endl(ans);
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
[JOI 2017 Final]JOIOI 王国
最小值 \(mn\) 和最大值 \(mx\) 显然不在一个集合中，不然答案固定。二分答案，判断根据题目描述，形成的图形一定为阶梯型，分四种情况讨论，判断是否存在包含 \(mn\) 的块里的数都小于等于 \(mn+x\)，包含 \(mx\) 的块里的数都大于等于 \(mx-x\)。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=2010;
int n,m,a[N][N],mn=inf,mx=-inf,Mn[N],Mx[N];
bool check(int x){
bool flag=1;
Mn[0]=Mx[n+1]=-inf,Mn[0]=Mn[n+1]=inf;
for(int i=1;i<=n;i++){
Mn[i]=Mn[i-1];
for(int j=1;j<=m;j++){
if(a[i][j]>mn+x){
Mn[i]=min(Mn[i],j);
}
}
}
for(int i=n;i;i--){
Mx[i]=Mx[i+1];
for(int j=1;j<=m;j++){
if(a[i][j]<mx-x){
Mx[i]=max(Mx[i],j);
}
}
if(Mx[i]>=Mn[i]){
flag=0;
}
}
if(flag){
return 1;
}
flag=1;
for(int i=1;i<=n;i++){
Mn[i]=Mn[i-1];
for(int j=1;j<=m;j++){
if(a[i][j]<mx-x){
Mn[i]=min(Mn[i],j);
}
}
}
for(int i=n;i;i--){
Mx[i]=Mx[i+1];
for(int j=1;j<=m;j++){
if(a[i][j]>mn+x){
Mx[i]=max(Mx[i],j);
}
}
if(Mx[i]>=Mn[i]){
flag=0;
}
}
if(flag){
return 1;
}
flag=1;
for(int i=n;i;i--){
Mn[i]=Mn[i+1];
for(int j=1;j<=m;j++){
if(a[i][j]<mx-x){
Mn[i]=min(Mn[i],j);
}
}
}
for(int i=1;i<=n;i++){
Mx[i]=Mx[i-1];
for(int j=1;j<=m;j++){
if(a[i][j]>mn+x){
Mx[i]=max(Mx[i],j);
}
}
if(Mx[i]>=Mn[i]){
flag=0;
}
}
if(flag){
return 1;
}
flag=1;
for(int i=n;i;i--){
Mn[i]=Mn[i+1];
for(int j=1;j<=m;j++){
if(a[i][j]>mn+x){
Mn[i]=min(Mn[i],j);
}
}
}
for(int i=1;i<=n;i++){
Mx[i]=Mx[i-1];
for(int j=1;j<=m;j++){
if(a[i][j]<mx-x){
Mx[i]=max(Mx[i],j);
}
}
if(Mx[i]>=Mn[i]){
flag=0;
}
}
if(flag){
return 1;
}
return 0;
}
void solve(){
read(n),read(m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
read(a[i][j]);
mx=max(mx,a[i][j]);
mn=min(mn,a[i][j]);
}
}
int l=0,r=mx-mn,ans;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)){
r=mid-1;
ans=mid;
}
else{
l=mid+1;
}
}
write_endl(ans);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
[JOI 2018 Final]美術展
按大小排序，如果已经选定了最大的和最小的，中间的肯定都可以选，它们只会影响价值和，答案不降。将贡献拆开，令 \(b_i\) 表示价值的前缀和，\(S-a_{\max}+a_{\min}=b_{i}-a_i+a_j-b_{j-1}\)，求出 \(a_j-b_{j-1}\) 的前缀最大值即可计算。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e18;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=5e5+10;
int n,b[N];
pii a[N];
void solve(){
read(n);
for(int i=1;i<=n;i++){
read(a[i].first),read(a[i].second);
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
b[i]=b[i-1]+a[i].second;
}
int mx=-inf,ans=-inf;
for(int i=1;i<=n;i++){
mx=max(mx,a[i].first-b[i-1]);
ans=max(ans,mx+b[i]-a[i].first);
}
write_endl(ans);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
[JOI 2018 Final]団子職人
如果两个团子冲突，则两个团子的 G 必然都在一条左下到右上的的斜线上。枚举斜线，令 \(f_{i,0/1/2}\) 表示在斜线上的该点的团子没有/是横着/是竖着，直接dp即可。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=3e3+10;
int n,m,ans,f[N][3];
char ch[N][N];
void solve(){
read(n),read(m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
ch[i][j]=getchar();
while(ch[i][j]!='R'&&ch[i][j]!='G'&&ch[i][j]!='W'){
ch[i][j]=getchar();
}
}
}
for(int s=2;s<=n+m;s++){
memset(f,0,sizeof(f));
int tmp=0;
for(int i=max(1,s-m),j=s-i;i<=n&&j;i++,j--){
f[i][0]=max(max(f[i-1][0],f[i-1][1]),f[i-1][2]);
if(ch[i][j]=='G'){
if(ch[i-1][j]=='R'&&ch[i+1][j]=='W'){
f[i][1]=max(f[i][1],max(f[i-1][0],f[i-1][1])+1);
}
if(ch[i][j-1]=='R'&&ch[i][j+1]=='W'){
f[i][2]=max(f[i][2],max(f[i-1][0],f[i-1][2])+1);
}
}
tmp=max(tmp,max(max(f[i][0],f[i][1]),f[i][2]));
}
ans+=tmp;
}
write_endl(ans);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
[JOI 1018 Final]定期券
一个显而易见的结论是两条路径只有一段重叠的。证明很容易，若 \(A\rightarrow B\rightarrow C\rightarrow D\)，其中 \(A\rightarrow B,C\rightarrow D\) 在最短路上，\(B\rightarrow C\) 不在最短路上，不如直接换成最短路上的路径上的路，因此只会有一段路径，这段路径要么正着经过要么反着经过，直接找到所有最短路上的边，正边建一层图，反边建一层图，跑分层图即可得到答案。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e18;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int M=2e5+10,N=4e5+10;
int n,m,s,t,st,ed,head[N],fir[N],tot,cnt,vis[N],d[N],c[N];
struct edge{
int u,v,w,nxt;
}e[M<<1],G[M<<4];
void add(int u,int v,int w){
e[++tot].v=v;
e[tot].u=u;
e[tot].w=w;
e[tot].nxt=head[u];
head[u]=tot;
}
void ins(int u,int v,int w){
G[++cnt].v=v;
G[cnt].w=w;
G[cnt].nxt=fir[u];
fir[u]=cnt;
}
void dij(){
for(int i=1;i<=n;i++){
vis[i]=0;
d[i]=inf;
}
d[s]=0;
priority_queue<pii>q;
q.push(mp(0,s));
while(!q.empty()){
int u=q.top().second;
q.pop();
if(vis[u]){
continue;
}
vis[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(d[v]>d[u]+w){
d[v]=d[u]+w;
q.push(mp(-d[v],v));
}
}
}
for(int i=1;i<=n;i++){
vis[i]=0;
c[i]=inf;
}
c[t]=0;
q.push(mp(0,t));
while(!q.empty()){
int u=q.top().second;
q.pop();
if(vis[u]){
continue;
}
vis[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(c[v]>c[u]+w){
c[v]=c[u]+w;
q.push(mp(-c[v],v));
}
}
}
for(int u=1;u<=n;u++){
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(d[u]+c[v]+w==d[t]){
ins(u+n,v+n,0);
ins(v+n*2,u+n*2,0);
}
}
}
}
void work(){
for(int i=1;i<=n*4;i++){
d[i]=inf;
vis[i]=0;
}
d[st]=0;
priority_queue<pii>q;
q.push(mp(0,st));
while(!q.empty()){
int u=q.top().second;
q.pop();
for(int i=fir[u];i;i=G[i].nxt){
int v=G[i].v,w=G[i].w;
if(d[v]>d[u]+w){
d[v]=d[u]+w;
q.push(mp(-d[v],v));
}
}
}
write_endl(d[ed+3*n]);
}
void solve(){
read(n),read(m);
read(s),read(t);
read(st),read(ed);
for(int i=1;i<=m;i++){
int u,v,w;
read(u),read(v),read(w);
add(u,v,w);
add(v,u,w);
ins(u,v,w);
ins(v,u,w);
ins(u+n*3,v+n*3,w);
ins(v+n*3,u+n*3,w);
}
for(int i=1;i<=n;i++){
ins(i,i+n,0);
ins(i,i+n*2,0);
ins(i+n,i+n*3,0);
ins(i+n*2,i+n*3,0);
}
dij();
work();
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}