记一场（伪）CF （Educational Codeforces Round 40 (Rated for Div. 2) ）

本文主要是介绍记一场（伪）CF （Educational Codeforces Round 40 (Rated for Div. 2) ），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

实际上是div2场…
考了半个多小时才想起来有这个比赛…
然后就看了看…（英语太菜了，十几二十分钟才能看懂一题）
只写了 D E F G(其中只有D E是考中写完的…)
D:
题目大意：求有多少不直接相交的点对，并且这个点对连上以后不能改变s- > t的最短路.
题解：两边SPFA完以后，直接暴力枚举点对即可.
c++代码如下：

#include<bits/stdc++.h>
#define rep(i,x,y) for(register int i = x ; i <= y; ++ i)
#define repd(i,x,y) for(register int i = x ; i >= y; -- i)
using namespace std;
template<typename T>inline void read(T&x)
{x = 0;char c;int sign = 1;do { c = getchar(); if(c == '-') sign = -1; }while(!isdigit(c));do { x = x * 10 + c - '0'; c = getchar(); }while(isdigit(c));x *= sign;
}const int N = 1e3 + 10;
int n,m,d1[N],d2[N],head[N],nxt[N << 1],to[N << 1],tot;
bool vis[N],dis[N][N];inline void add(int x,int y)
{to[tot] = y;nxt[tot] = head[x];head[x] = tot++;
}inline void SPFA(int*d,int s)
{rep(i,1,n) d[i] = 100000;d[s] = 0;queue<int>q;q.push(s);while(!q.empty()){int x = q.front(); q.pop(); vis[x] = 0;for(register int i = head[x];~i;i = nxt[i])if(d[to[i]] > d[x] + 1){d[to[i]] = d[x] + 1;if(!vis[to[i]]) vis[to[i]] = 1,q.push(to[i]);}} 
}int main()
{memset(head,-1,sizeof head);int s,t;read(n); read(m); read(s); read(t);rep(i,1,m){int u,v;read(u); read(v);dis[u][v] = dis[v][u] = 1;add(u,v); add(v,u);}SPFA(d1,s);SPFA(d2,t);int ans = 0;rep(i,1,n)rep(j,i + 1,n)if(!dis[i][j] && d1[t] <= d1[i] + d2[j] + 1 && d1[t] <= d1[j] + d2[i] + 1)ans++;cout << ans << endl; return 0;
}

E:
题意：很多个杯子，杯子有一个容量和温度，在满足兑出来的水的温度是t的前提下，兑的水尽可能多
题解：考虑先把所有的水兑在一起，如果已经是t的温度肯定直接输出，不然看温度比 t 高还是低，然后考虑肯定是温度最高/最低的温度需要另兑的水最多，那么肯定优先去掉这些水，直到温度低于/高于t，此时说明在兑这杯水以后温度低于/高于t，兑完以后高于/低于t，那么所以兑这杯水的一定量即可达到最大体积…计算一下即可。

注意：卡精度

c++代码如下:

#include<bits/stdc++.h>
#define rep(i,x,y) for(register int i = x ; i <= y; ++ i)
#define repd(i,x,y) for(register int i = x ; i >= y; -- i)
using namespace std;
typedef long long ll;
template<typename T>inline void read(T&x)
{x = 0;char c;int sign = 1;do { c = getchar(); if(c == '-') sign = -1; }while(!isdigit(c));do { x = x * 10 + c - '0'; c = getchar(); }while(isdigit(c));x *= sign;
}
const int N = 2e5 + 10;
int n; ll t;
struct Str { ll s,t; }a[N];
ll sum1,sum2;
const bool cmp(Str a,Str b) { return a.t < b.t; }int main()
{read(n);read(t);rep(i,1,n) read(a[i].s);rep(i,1,n) read(a[i].t);rep(i,1,n){sum1 += a[i].t*a[i].s;sum2 += a[i].s;}sort(a + 1,a + 1 + n,cmp);if(sum1 == t * sum2) { cout << fixed << setprecision(15) << sum2  << '\n'; return 0; }if(sum1 > t * sum2){repd(i,n,1){sum1 -= a[i].s*a[i].t;sum2 -= a[i].s;if(sum1 <= t * sum2){cout << fixed << setprecision(15) << sum2 + ((sum1 - sum2 * t) / ((double)t - a[i].t)) << '\n';return 0;}}}else{rep(i,1,n){sum1 -= a[i].s*a[i].t;sum2 -= a[i].s;if(sum1 >= t * sum2){cout << fixed << setprecision(15) << sum2 + ((sum1 - sum2 * t) / ((double)t - a[i].t)) << '\n';return 0;}}}cout << fixed << setprecision(15) << 0 << endl;return 0;
}

F：
题意：有一个3*m的方格，一开始（2，1）有一个棋子，棋子可以向右上、右中、右下跳，求跳到（2，m）的方案数,并且方格有一些障碍，障碍不能被到达…
题解:看到数据范围（1e18）肯定想到了矩阵快速幂，实际上发现状态也很好处理，只用在每个障碍前停下计算答案，然后更新now数组继续计算即可：

c++代码如下：

#include<bits/stdc++.h>
#define rep(i,x,y) for(register int 
i = x ; i <= y; ++ i)
#define repd(i,x,y) for(register int i = x ; i >= y; -- i)
using namespace std;
typedef long long ll;
template<typename T>inline void read(T&x)
{x = 0;char c;int sign = 1;do { c = getchar(); if(c == '-') sign = -1; }while(!isdigit(c));do { x = x * 10 + c - '0'; c = getchar(); }while(isdigit(c));x *= sign;
}
const int N = 2e4 + 10,p = 1e9+7;
int n,cnt,t[4];ll m,lst = 1;
struct Str { ll x,s,op; } a[N];
const bool cmp(Str a,Str b) { return a.s < b.s; }struct Matrix
{int a[4][4];inline void clear() { rep(i,1,3) rep(j,1,3) a[i][j] = 0; }inline void print() { rep(i,1,3) rep(j,1,3) printf("%d%c",a[i][j],j==3?'\n':' ');puts(""); }Matrix operator * (const Matrix b){Matrix c;c.clear();rep(i,1,3) rep(j,1,3) rep(k,1,3)c.a[i][j] = (c.a[i][j] + 1ll*a[i][k] * b.a[k][j]) % p;return c;}
}ans,now;Matrix quick_pow(Matrix x,ll y)
{Matrix ans;ans.clear();rep(i,1,3) ans.a[i][i] = 1;while(y){if(y & 1) ans = x * ans;x = x * x ;y >>= 1;}return ans ;
}int main()
{read(n); read(m);rep(i,1,n){ll x,l,r;read(x); read(l); read(r);a[++cnt].x = x; a[cnt].s = l;a[cnt].op = -1;a[++cnt].x = x; a[cnt].s = r + 1;a[cnt].op = 1;}sort(a + 1, a + 1 + cnt,cmp);ans.clear(); now.clear();ans.a[2][1] = 1;rep(i,1,3) rep(j,1,3) now.a[i][j] = 1;now.a[1][3] = now.a[3][1] = 0;rep(i,1,cnt){if(a[i].s != lst + 1){Matrix x = quick_pow(now,a[i].s - 1 - lst);ans = x * ans ;}t[a[i].x] += a[i].op;if(a[i].x == 1) now.a[1][1] = !t[1],now.a[1][2] = !t[1],now.a[1][3] = 0; if(a[i].x == 2) now.a[2][1] = !t[2],now.a[2][2] = !t[2],now.a[2][3] = !t[2];if(a[i].x == 3) now.a[3][1] = 0,now.a[3][2] = !t[3],now.a[3][3] = !t[3];lst = a[i].s - 1;} ans = quick_pow(now,m - lst) * ans;cout << ans.a[2][1] << endl;return 0;
}

G题：
题意：n 个弓箭手，第 i 个可以保护 i-r ~ i+r 范围的所有地方，你可以加 k 个弓箭手到任何地方..防御值是一个地方被多少弓箭手保护，如何分配使最小防御值最大。
题解：前缀和能直接算出一开始每个点有多少防御值，然后二分答案即可，明显一个弓箭手放在最右边能放的位置上…比前面几题似乎简单得多
c++代码如下：

#include<bits/stdc++.h>
#define rep(i,x,y) for(register int i = x ; i <= y; ++ i)
#define repd(i,x,y) for(register int i = x ; i >= y; -- i)
using namespace std;
typedef long long ll;
template<typename T>inline void read(T&x)
{x = 0;char c;int sign = 1;do { c = getchar(); if(c == '-') sign = -1; }while(!isdigit(c));do { x = x * 10 + c - '0'; c = getchar(); }while(isdigit(c));x *= sign;
}const int N = 1e6 + 500;
int n,r;ll k,a[N],sum[N],sign[N];inline bool check(ll num)
{memset(sign,0,sizeof sign);ll x = k;ll sum = 0;rep(i,1,n){sum -= sign[i];if(a[i] + sum < num){x -= num - a[i] - sum;sign[i + 2 * r + 1] += num - a[i] - sum;sum += num - a[i] - sum;}if(x < 0) return false;}return true;
}int main()
{read(n); read(r); read(k);rep(i,1,n) read(a[i]);rep(i,1,n) sum[i] = sum[i - 1] + a[i];rep(i,1,n) a[i] = sum[min(i + r,n)] - sum[max(i - r - 1,0)];ll l = 0,r = 2e18,mid,ans;while(l <= r){if(check(mid = l + r >> 1)) l = mid + 1,ans = mid;else r = mid - 1;}cout << ans << endl;return 0;
}