暑假集训test-8-31(pm)

以为可以AK，结果t3没有调出来，然后被林巨踩了。

everyday被踩，很开心。

林巨真的好巨啊，这么多天已经总计虐我75分了。

1.玩具装箱

第一眼还以为是那道斜率优化dp,结果是个签到水题。

 1 //Achen
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<cstring>
 5 #include<cstdlib>
 6 #include<vector>
 7 #include<cstdio>
 8 #include<queue>
 9 #include<cmath>
10 #include<set>
11 #include<map>
12 #define Formylove return 0
13 #define For(i,a,b) for(int i=(a);i<=(b);i++)
14 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)
15 const int N=20007;
16 typedef long long LL;
17 typedef double db;
18 using namespace std;
19 int n,m;
20 LL k,f[N],a[N];
21 
22 template<typename T>void read(T &x)  {
23     char ch=getchar(); x=0; T f=1;
24     while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
25     if(ch=='-') f=-1,ch=getchar();
26     for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
27 }
28 
29 #define ANS
30 int main() {
31 #ifdef ANS
32     freopen("toy.in","r",stdin);
33     freopen("toy.out","w",stdout);
34 #endif
35     read(n); read(m); read(k);
36     For(i,1,n) read(a[i]);
37     memset(f,127/3,sizeof(f));
38     f[0]=0;
39     For(i,1,n) {
40         LL mi=a[i],mx=a[i];
41         Rep(j,i-1,max(0,i-m)) {
42             f[i]=min(f[i],f[j]+k+(mx-mi)*(i-j));
43             mi=min(mi,a[j]);
44             mx=max(mx,a[j]);
45         }
46     }
47     printf("%lld
",f[n]);
48     Formylove;
49 }

View Code

2.铁路运费

林巨写的比较优美，我比较傻就用set水过去了。

边权从1到2等于删边。

bfs树上树边和指向深度比它小的点的边有用，分别用set存一下。每次删树边的时候在另一个set里找还有没有可以用的父亲，有就连成新的树边，退出，没有就把它标记了然后删除它到它儿子的边，递归操作它儿子。

  1 //Achen
  2 #include<algorithm>
  3 #include<iostream>
  4 #include<cstring>
  5 #include<cstdlib>
  6 #include<vector>
  7 #include<cstdio>
  8 #include<queue>
  9 #include<cmath>
 10 #include<set>
 11 #include<map>
 12 #define Formylove return 0
 13 #define For(i,a,b) for(int i=(a);i<=(b);i++)
 14 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)
 15 const int N=2e5+7;
 16 typedef long long LL;
 17 typedef double db;
 18 using namespace std;
 19 int n,m,q,ans,no[N];
 20 
 21 template<typename T>void read(T &x)  {
 22     char ch=getchar(); x=0; T f=1;
 23     while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
 24     if(ch=='-') f=-1,ch=getchar();
 25     for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
 26 }
 27 
 28 struct edge {
 29     int u,v;
 30 }e[N];
 31 
 32 int ecnt,fir[N],nxt[N<<1],to[N<<1];
 33 void init() { ecnt=0; memset(fir,0,sizeof(fir)); }
 34 void add(int u,int v) {
 35     nxt[++ecnt]=fir[u]; fir[u]=ecnt; to[ecnt]=v;
 36     nxt[++ecnt]=fir[v]; fir[v]=ecnt; to[ecnt]=u;
 37 }
 38 
 39 int d[N],fid[N];
 40 queue<int>que;
 41 set<int>s[N],son[N];
 42 
 43 void bfs(int s) {
 44     For(i,1,n) d[i]=n;
 45     d[s]=0;
 46     que.push(s);
 47     while(!que.empty()) {
 48         int x=que.front();
 49         que.pop();
 50         for(int i=fir[x];i;i=nxt[i]) if(d[to[i]]==n) {
 51             d[to[i]]=d[x]+1;
 52 
 53             son[x].insert(to[i]);
 54             que.push(to[i]); 
 55         }
 56     } 
 57 }
 58 
 59 void solve(int x,int fa) {
 60     son[fa].erase(x);
 61     s[x].erase(fa); 
 62     while(s[x].size()) {
 63         int y=*s[x].begin();
 64         if(!no[y]) { son[y].insert(x); return; }
 65         s[x].erase(y); 
 66     }
 67     ans++;
 68     no[x]=1;
 69     while(son[x].size()) {
 70         int y=*son[x].begin();
 71         solve(y,x);
 72     } 
 73 }
 74 
 75 #define ANS
 76 int main() {
 77 #ifdef ANS
 78     freopen("train.in","r",stdin);
 79     freopen("train.out","w",stdout);
 80 #endif
 81     read(n); read(m); read(q);
 82     For(i,1,m) {
 83         read(e[i].u); read(e[i].v); 
 84         add(e[i].u,e[i].v);
 85     }
 86     bfs(1);
 87     For(x,1,n) {
 88         for(int i=fir[x];i;i=nxt[i]) if(d[to[i]]+1==d[x]) 
 89             s[x].insert(to[i]);
 90     }
 91     For(ti,1,q) {
 92         int id;
 93         read(id);
 94         int u=e[id].u,v=e[id].v;
 95         if(son[u].find(v)!=son[u].end()||son[v].find(u)!=son[v].end()) {
 96             if(d[u]+1==d[v]) solve(v,u);
 97             else solve(u,v);
 98         }
 99         else {
100             if(s[v].find(u)!=s[v].end()) s[v].erase(u); 
101             else if(s[u].find(v)!=s[u].end()) s[u].erase(v);  
102         }
103         printf("%d
",ans); 
104     }
105     Formylove;
106 }
107 /*
108 5 6 5
109 1 2
110 1 3
111 4 2
112 3 2
113 2 5
114 5 3
115 5
116 2
117 4
118 1
119 3
120 */

View Code

3.城墙

对于每个点维护它往右往下能到的最长没有x的长度记作a[i][j]，往左往上能到达的没有x的最长长度b[i][j]。沿着对角线扫，用树状数组维护一下，把a放进树状数组，用b和L限制查询范围。

  1 //Achen
  2 #include<algorithm>
  3 #include<iostream>
  4 #include<cstring>
  5 #include<cstdlib>
  6 #include<vector>
  7 #include<cstdio>
  8 #include<queue>
  9 #include<cmath>
 10 #include<set>
 11 #include<map>
 12 #define Formylove return 0
 13 #define For(i,a,b) for(int i=(a);i<=(b);i++)
 14 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)
 15 const int N=3007;
 16 typedef long long LL;
 17 typedef double db;
 18 using namespace std;
 19 int n,m,L,tot; 
 20 int mp[N][N],s[N][N],x[N][N],z[N][N],y[N][N],a[N][N],b[N][N];
 21 
 22 template<typename T>void read(T &x)  {
 23     char ch=getchar(); x=0; T f=1;
 24     while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
 25     if(ch=='-') f=-1,ch=getchar();
 26     for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
 27 }
 28 
 29 void pre() {
 30     For(i,1,n) {
 31         For(j,1,m) z[i][j]=mp[i][j]?0:z[i][j-1]+1; 
 32         Rep(j,m,1) y[i][j]=mp[i][j]?0:y[i][j+1]+1;
 33     }
 34     For(j,1,m) {
 35         For(i,1,n) s[i][j]=mp[i][j]?0:s[i-1][j]+1;
 36         Rep(i,n,1) x[i][j]=mp[i][j]?0:x[i+1][j]+1;
 37     }
 38     For(i,1,n) For(j,1,m) {
 39         a[i][j]=min(y[i][j],x[i][j]);
 40         b[i][j]=min(z[i][j],s[i][j]);
 41     }
 42 }
 43 
 44 int sum[N],up;
 45 void add(int x,int v) {
 46     if(!x) return; 
 47     for(int i=x;i<=up;i+=(i&(-i)))
 48         sum[i]+=v;
 49 }
 50 
 51 int qry(int x) {
 52     int rs=0;
 53     for(int i=x;i;i-=(i&(-i)))
 54         rs+=sum[i];
 55     return rs;
 56 }
 57 
 58 vector<int>vc[N],vc2[N];
 59 void solve() {
 60     LL ans=0;
 61     For(ty,1,m) {
 62         int x=1,y=ty;
 63         memset(sum,0,sizeof(sum));
 64         For(i,0,up) vc[i].clear(),vc2[i].clear(); 
 65         For(i,0,up) {
 66             if(x+i>n||y+i>m) break;
 67             if(i-L+1>=0&&i-L+1>i-b[x+i][y+i]) {
 68                 vc2[i-L+1].push_back(i);  
 69                 if(i-b[x+i][y+i]>=0) 
 70                     vc[i-b[x+i][y+i]].push_back(i);
 71             } 
 72         }
 73         For(i,0,up) {
 74             if(x+i>n||y+i>m) break;
 75             add(a[x+i][y+i]+i,1);
 76             int upp=vc[i].size();
 77             For(j,0,upp-1) 
 78                 ans-=qry(up)-qry(vc[i][j]);
 79             upp=vc2[i].size();
 80             For(j,0,upp-1)
 81                 ans+=qry(up)-qry(vc2[i][j]);
 82         }
 83     }
 84     For(tx,2,n) {
 85         int x=tx,y=1;
 86         memset(sum,0,sizeof(sum));
 87         For(i,0,up) vc[i].clear(),vc2[i].clear(); 
 88         For(i,0,up) {
 89             if(x+i>n||y+i>m) break;
 90             if(i-L+1>=0&&i-L+1>i-b[x+i][y+i]) {
 91                 vc2[i-L+1].push_back(i);  
 92                 if(i-b[x+i][y+i]>=0) 
 93                     vc[i-b[x+i][y+i]].push_back(i);
 94             } 
 95         }
 96         For(i,0,up) {
 97             if(x+i>n||y+i>m) break;
 98             add(a[x+i][y+i]+i,1);
 99             int upp=vc[i].size();
100             For(j,0,upp-1) 
101                 ans-=qry(up)-qry(vc[i][j]);
102             upp=vc2[i].size();
103             For(j,0,upp-1)
104                 ans+=qry(up)-qry(vc2[i][j]);
105         }
106     }
107     printf("%lld
",ans);
108 }
109 
110 #define ANS
111 int main() {
112 #ifdef ANS
113     freopen("rampart.in","r",stdin);
114     freopen("rampart.out","w",stdout);
115 #endif
116     read(n); read(m); read(L); read(tot);
117     up=max(n,m);
118     For(i,1,tot) {
119         int x,y;
120         read(x); read(y);
121         mp[x][y]=1;
122     }
123     pre(); 
124     solve();
125     Formylove;
126 }

View Code