solve：4/11
补题：6/11
补题：zz
这是一道分类讨论的题目，有一个规律就是如果必须要从第一个区到第二个区，那么最多转区两次（1到2一次，2到1一次），然后分类讨论即可，只要细心一定能做出来。
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<math.h>
#include<cmath>
#include<time.h>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<algorithm>
#include<numeric>
#include<stack>
#include<bitset>
#include<unordered_map>
const int maxn = 0x3f3f3f3f;
const double EI = 2.71828182845904523536028747135266249775724709369995957496696762772407663035354594571382178525166427;
const double PI = 3.141592653589793238462643383279;
//#ifdef TRUETRUE
//#define gets gets_s
//#endif
using namespace std;
int c[][];
int z[][], cnt[];
int d[];
int main(void)
{
//ios::sync_with_stdio(false);
int n, rr, k, m, s, i, x, y, l1, l2, r1, r2, ans, l, r, j;
while (~scanf("%d %d %d %d %d", &n, &rr, &m, &k, &s))
{
memset(c, , sizeof(c));
cnt[] = ;
cnt[] = ;
for (i = ; i < rr; i++)
{
scanf("%d %d", &x, &y);
if (x == s && y == )
{
continue;
}
c[y][x] = ;
z[y][cnt[y]++] = x;
}
for (i = ; i < m; i++)
{
scanf("%d", d + i);
}
sort(z[], z[] + cnt[]);
sort(z[], z[] + cnt[]);
l1 = -;
l2 = -;
r1 = -;
r2 = -;
if (cnt[])
{
l1 = z[][];
r1 = z[][cnt[] - ];
}
if (cnt[])
{
l2 = z[][];
r2 = z[][cnt[] - ];
}
ans = ;
if (l2 != -)
{
ans += k * ;
}
l = min(l1, l2);
if (l1 == -)
{
l = l2;
}
else if (l2 == -)
{
l = l1;
}
r = max(r1, r2);
d[m++] = ;
d[m++] = n;
d[m++] = n + ;
sort(d, d + m);
/*for (i = 0;i < m;i++)
{
printf("%d ", d[i]);
}
printf("\n");*/
//printf("l = %d r = %d\n", l, r);
if (r <= s && r != - && l != -)
{
//printf("l = %d r = %d\n",l,r);
for (i = ; i < m; i++)
{
if (d[i] <= l && d[i + ] > l)
{
break;
}
}
ans += s - d[i];
//printf("ans = %d\n",ans);
if (l2 != -)
{
for (j = ; j < m; j++)
{
if (d[j] >= r2)
{
break;
}
}
ans += d[j] - d[i];
ans += abs(s - d[j]);
}
else
{
ans += s - d[i];
}
}
else if (l >= s && r != - && l != -)
{
for (i = ; i < m; i++)
{
if (d[i] >= r)
{
break;
}
}
ans += d[i] - s;
if (l2 != -)
{
for (j = m - ; j >= ; j--)
{
if (d[j] <= l2)
{
break;
}
}
ans += d[i] - d[j];
ans += abs(s - d[j]);
}
else
{
ans += d[i] - s;
}
}
else if (l <= s && r >= s && r != - && l != -)
{
for (i = ; i < m; i++)
{
if (d[i] <= l && d[i + ] > l)
{
break;
}
}
//printf(" %d\n",ans);
ans += * (s - d[i]);
//printf(" %d %d %d %d %d\n", ans,d[i],i,l,r);
for (i = ; i < m; i++)
{
if (d[i] <= r && d[i + ] >= r)
{
break;
}
}
ans += * (d[i + ] - s);
//printf(" %d %d\n", ans,d[i + 1]);
}
printf("%d\n", ans);
}
return ;
}
Code:pai爷
Thinking: pai爷 KK
dp[ i ][ j ][ k ]表示 i 行 j 列 在第 k 秒的时候吃到的最多的豆豆数量，从五个方向转移（上下左右加自己）。k的范围最大只有1018*10，然后用滚动数组滚动掉，就可以AC了。
补充：div1 1018变成了10^18，会有周期，尚未证明，k，k+t，k+2t。
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int ans=,n,m,c,now=,X1,X2,Y1,Y2,f[][][],t[][];
void solve(int a,int b,int c,int d,int k) {
if(t[a][b]!= && (k%t[a][b]==)) f[!now][a][b]=max(f[now][c][d]+,f[!now][a][b]);
else f[!now][a][b]=max(f[now][c][d],f[!now][a][b]);
}
int main() {
scanf("%d%d%d",&n,&m,&c);
for(int i=; i<=n; i++)
for(int j=; j<=m; j++) scanf("%d",&t[i][j]);
scanf("%d%d%d%d",&X1,&Y1,&X2,&Y2);
for(int k=; k<=; k++)
for(int i=; i<=n; i++)
for(int j=; j<=m; j++) f[k][i][j]=-;
f[now][X1][Y1]=;
for(int k=; k<=; k++) {
for(int i=; i<=n; i++)
for(int j=; j<=m; j++)
if(f[now][i][j]!=-) {
solve(i+,j,i,j,k);
solve(i-,j,i,j,k);
solve(i,j+,i,j,k);
solve(i,j-,i,j,k);
solve(i,j,i,j,k);
if(f[!now][X2][Y2]>=c) ans=k;
}
if(ans) break;
now=!now;
}
printf("%d\n",ans);
}
unsolved
unsolved
补题：kk
树形dp，比赛没人做，以为是难题。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#define CLR(a,b) memset(a,b,sizeof(a));
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=;
int head[maxn],tot,n;
bool vis[maxn];
int f[maxn],d[maxn];
int dp[][maxn];
struct edge{
int v,Next;
}a[maxn<<];
void init(){
tot=,CLR(head,-);
CLR(vis,false);
CLR(dp,);
}
void addv(int u,int v)
{
a[++tot].v=v;
a[tot].Next=head[u];
head[u]=tot;
}
void tdfs(int u,int fa){
int flag=;
vis[u]=;
dp[][u]=;
dp[][u]=f[u];
for(int i=head[u];i!=-;i=a[i].Next)
{
int v=a[i].v;
if(v==fa)continue;
tdfs(v,u);
flag=;
dp[][u]+=max(dp[][v],dp[][v]);
dp[][u]+=max(dp[][v],dp[][v]-d[min(u,v)]);
}
}
int main(){
cin>>n;
init();
for(int i=;i<=n;i++)
{
scanf("%d",&f[i]);
}
for(int i=;i<=n;i++)
{
scanf("%d",&d[i]);
}
for(int i=;i<=n;i++)
{ if(i%==)
{
addv(i,*i+);
addv(*i+,i);
}
if(i%==){
addv(i,i/);
addv(i/,i);
}
}
int ans=;
for(int i=;i<=n;i++)
{
if(vis[i]==){
tdfs(i,);
ans+=max(dp[][i],dp[][i]);
}
}
printf("%d\n",ans);
}
Code：KK
Thinking：KK
对于一座山，如果要砍，就肯定要砍到（K+第一座山的高度），将这部分额外的花费加到边的权值上就好了，双向边要分开建，权值不一定一样，然后dijkstra跑一跑，水题。
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<math.h>
#include<cmath>
#include<time.h>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<algorithm>
#include<numeric>
#include<stack>
#include<bitset>
//#include<unordered_map>
const int inf = 0x3f3f3f3f;
const double EI = 2.71828182845904523536028747135266249775724709369995957496696762772407663035354594571382178525166427;
const double PI = 3.141592653589793238462643383279;
const int maxn=;
using namespace std;
typedef long long ll;
int n,m;
ll k;
int head[maxn],tot;
ll dis[maxn]; struct edge{
int v;
ll w;
int Next;
}a[maxn<<];
bool vis[maxn];
ll h[maxn];
void init(){
tot=,memset(head,-,sizeof(head));
}
void addv(int u,int v,ll w)
{
a[++tot].v=v;
a[tot].w=w;
a[tot].Next=head[u];
head[u]=tot;
}
priority_queue< pair<ll,int>>q;
void dijkstra(){
memset(vis,false,sizeof(vis));
memset(dis,0x3f,sizeof(dis));
dis[]=;
q.push(make_pair(,));
while(!q.empty()){
int x=q.top().second;
q.pop();
if(vis[x])continue;
vis[x]=;
for(int i=head[x];i!=-;i=a[i].Next)
{
int y=a[i].v;
ll w=a[i].w;
if(dis[y]>dis[x]+w){
dis[y]=dis[x]+w;
q.push(make_pair(-dis[y],y));
}
}
}
}
int main(void)
{
//ios::sync_with_stdio(false);
cin>>n>>m>>k;
init();
scanf("%lld",&h[]);
k+=h[];
for(int i=;i<=n;i++)
{
scanf("%lld",&h[i]);
}
int u,v;
ll w;
while(m--)
{
scanf("%d%d%lld",&u,&v,&w);
if(h[v]>=k)
addv(u,v,w+(h[v]-k)*(h[v]-k));
else addv(u,v,w);
if(h[u]>=k)
addv(v,u,w+(h[u]-k)*(h[u]-k));
else addv(v,u,w);
}
dijkstra();
printf("%lld\n",dis[n]);
return ;
}
unsolved
unsolved
Code：pai爷
Thinking：pai爷
div 2 树状数组+dp思想 O(n*n*log（n））
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int P=1e9+;
int n,p[],w[],c[],q[][];
int ans=;
inline int lowbit(int x){return x&-x;}
void add(int x,int y)
{
for(;x<=n;x+=lowbit(x)) c[x]=(c[x]+y)%P;
}
int sum(int x)
{
int tmp=;
for(;x;x-=lowbit(x)) tmp=(tmp+c[x])%P;
return tmp;
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&p[i]);
for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++)
{
if(p[i]<p[j])
{
q[i][]++;
q[i][q[i][]]=j;
//printf("%d %d\n",i,j);
}
}
for(int i=n;i>=;i--)
{
w[i]=sum(p[i]-);
ans=(ans+w[i])%P;
//printf("%d\n",ans);
w[i]++;
for(int j=;j<=q[i][];j++) add(p[q[i][j]],w[q[i][j]]);
}
printf("%d\n",ans);
}
Code：zz
Thinking：KK zz
div2：由于m最大只有一千，所以从（m+1）/2到1枚举最后我需要买的物品，每次和当前答案更新。如一个人的物品比自己需要买的多或一样多，那肯定先把多余这部分的全部买走，如果发现不够，那么就在剩下的所有里面挑最便宜的；如果发现买完那些比自己大的，就已经超出当前的值了，说明不合法，就不更新答案。用multiset完成以上操作。
div1：m变成一万，不能枚举，想到二分，发现中间有一段区间虽然都是合法的，但是并不是买的物品越少钱越少（买的物品多了，强制买的物品就少，然后不足的就可以从其他物品里挑最便宜的），所以不满足二分的性质，三分好像可以做（wls吐槽好像二字），标算是线段树？还不会。
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<math.h>
#include<cmath>
#include<time.h>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<algorithm>
#include<numeric>
#include<stack>
#include<bitset>
//#include<unordered_map>
const int inf = 0x3f3f3f3f;
const int maxn=;
using namespace std;
typedef long long ll;
struct s
{
long long c[];
int cnt;
}z[];
multiset<long long>st;
multiset<long long>::iterator it;
inline bool comp(ll a,ll b)
{
return a > b;
}
int main(void)
{
//ios::sync_with_stdio(false);
int n,m,i,z2,j,num,x,k;
long long z1,sum,ans,ss;
while(~scanf("%d %d",&n,&m))
{
st.clear();
for(i = ;i <= n;i++)
{
z[i].cnt = ;
}
for(i = ;i < m;i++)
{
scanf("%lld %d",&z1,&z2);
z[z2].c[z[z2].cnt++] = z1;
st.insert(z1);
}
for(i = ;i <= n;i++)
{
sort(z[i].c,z[i].c + z[i].cnt,comp);
}
sum = ;
num = ;
ans = ;
for(i = m / + ;i >= ;i--)
{
for(j = ;j <= n;j++)
{
if(z[j].cnt >= i)
{
while(z[j].cnt >= i)
{
num++;
sum += z[j].c[z[j].cnt - ];
st.erase(st.find(z[j].c[z[j].cnt - ]));
z[j].cnt--;
}
}
}
if(num == i)
{
ans = min(sum,ans);
}
else if(num < i)
{
ss = sum;
x = i - num;
for(it = st.begin();it != st.end();it++)
{
sum += *it;
x--;
if(x == )
{
break;
}
}
ans = min(sum,ans);
sum = ss;
}
}
printf("%lld\n",ans);
}
return ;
}
unsolved
建bfs树
训练总结:
KK: 简单dp听了pai爷的一些思路马上意会到正解。最短路看错样例，看清后秒解，然后oj的排名炸了，以为今天只能做两题，所以在梦游想题，后来发现J题数据量小，想了一下想到div2的正解，被zz优化了一下，刚好过了，自己写可能会wa一发（因为没有二分的性质，但是自己写可能会找到一个答案就直接break），以后训练要认真，很多题都是可以思考的，不到最后不要放弃。
pai爷：做题的时候缺少验证吧，不够认真对待题目，思路要清晰，想法很多，错误想法也很多。之后要大胆猜测以及大胆验证。
zz：一开局看到了B，感觉和以前做的一道题很像，想到可能是一个三重循环的dp，但是时间那一维和状态转移方程没想好，就没说，看其他题去了；后来oj出了问题，基本上没更新，题目基本上没什么思路，过了很久以后，kk跟我说了J题的暴力做法，我看了看n和m才一千，感觉行，后来在写的时候发现太暴力是要n^3的，就用multiset降到了n*n*log(n)，刚好过（因为comp函数写错了wa了，哭了）。