A
B
C
D
给你一个联通图 给定S,T 要求你加一条边使得ST的最短距离不会减少 问你有多少种方法
因为N<=1000 所以N^2枚举边数 迪杰斯特拉两次 求出Sdis 和 Tdis 如果dis[i]+dis[j]+1>=distance(s,t)&&dis[j]+dis[i]+1>=distance(i,j)就为一条要求边
#include <bits/stdc++.h> #define PI acos(-1.0) #define mem(a,b) memset((a),b,sizeof(a)) #define TS printf("!!! ") #define pb push_back #define inf 1e9 //std::ios::sync_with_stdio(false); using namespace std; //priority_queue<int,vector<int>,greater<int>> que; get min const double eps = 1.0e-10; const double EPS = 1.0e-4; typedef pair<int, int> pairint; typedef long long ll; typedef unsigned long long ull; //const int maxn = 3e5 + 10; const int maxn = 100005; const int turn[4][2] = {{1, 0}, { -1, 0}, {0, 1}, {0, -1}}; const int turn2[8][2] = {{1, 0}, { -1, 0}, {0, 1}, {0, -1}, {1, -1}, { -1, -1}, {1, 1}, { -1, 1}}; //priority_queue<int, vector<int>, less<int>> que; //next_permutation string a; vector<int> gra[1005]; int from, to; int anser; int n, m, s, t; int sum; int tong[1005][1005]; int sdis[1005]; int tdis[1005]; void getsdis() { for (int i = 1; i <= n; i++) { if (i == s) { continue; } sdis[i] = INT_MAX; } queue<int> que; que.push(s); while (!que.empty()) { int now = que.front(); que.pop(); int len = gra[now].size(); for (int i = 0; i < len; i++) { int to = gra[now][i]; if (sdis[to] > sdis[now] + 1) { sdis[to] = sdis[now] + 1; que.push(to); } } } } void gettdis() { for (int i = 1; i <= n; i++) { if (i == t) { continue; } tdis[i] = INT_MAX; } queue<int> que; que.push(t); while (!que.empty()) { int now = que.front(); que.pop(); int len = gra[now].size(); for (int i = 0; i < len; i++) { int to = gra[now][i]; if (tdis[to] > tdis[now] + 1) { tdis[to] = tdis[now] + 1; que.push(to); } } } } int main() { cin >> n >> m >> s >> t; for (int i = 1; i <= m; i++) { scanf("%d %d", &from, &to); gra[from].pb(to); gra[to].pb(from); tong[from][to] = tong[to][from] = 1; } sum = (n - 1) * n / 2; getsdis(); gettdis(); int mindis = sdis[t]; // cout << mindis << endl; // for (int i = 1; i <= n; i++) // { // cout << sdis[i] << " "; // } // cout << endl; // for (int i = 1; i <= n; i++) // { // cout << tdis[i] << " "; // } // cout << endl; for (int i = 1; i <= n - 1; i++) { for (int j = i + 1; j <= n; j++) { if (tong[i][j]) { continue; } if (sdis[i] + tdis[j] + 1 >= mindis && sdis[j] + tdis[i] + 1 >= mindis) { anser++; } } } cout << anser << endl; return 0; }
E
给你N个水管 每个水管流出的水的温度是恒定的 但是流量是可控的 给你一个温度T问你每秒最多的流量是多少
按每个水管的温度排序 然后贪心
#include <bits/stdc++.h> #define PI acos(-1.0) #define mem(a,b) memset((a),b,sizeof(a)) #define TS printf("!!! ") #define pb push_back #define inf 1e9 //std::ios::sync_with_stdio(false); using namespace std; //priority_queue<int,vector<int>,greater<int>> que; get min const double eps = 1.0e-10; typedef pair<int, int> pairint; typedef long long ll; typedef unsigned long long ull; //const int maxn = 3e5 + 10; const int maxn = 100005; const int turn[4][2] = {{1, 0}, { -1, 0}, {0, 1}, {0, -1}}; const int turn2[8][2] = {{1, 0}, { -1, 0}, {0, 1}, {0, -1}, {1, -1}, { -1, -1}, {1, 1}, { -1, 1}}; //priority_queue<int, vector<int>, less<int>> que; //next_permutation //double a[200005]; //double t[200005]; pair<double, double> wendu[200005]; int n; double T; double anser; int flag = 1; double nowx, nowy; bool cmp(pair<double, double> a, pair<double, double> b) { if (a.second == b.second) { return a.first < b.first; } return a.second < b.second; } int main() { cin >> n >> T; for (int i = 1; i <= n; i++) { scanf("%lf", &wendu[i].first); } for (int i = 1; i <= n; i++) { scanf("%lf", &wendu[i].second); } sort(wendu + 1, wendu + 1 + n, cmp); int left = 1; int right = n; for (int i = 1; i <= n; i++) { nowx += 1.0 * wendu[i].first * wendu[i].second; nowy += wendu[i].first; } //printf("%.8f ", nowx); //printf("%.8f ", nowy); if (fabs(nowx / nowy - T) < eps) { printf("%.7f ", nowy); return 0; } else if (nowx / nowy - T > eps) { while (fabs(nowx / nowy - T) > eps) { if (wendu[right].second <= T) { flag = 0; break; } double nextx, nexty; nextx = nowx - 1.0 * wendu[right].first * wendu[right].second; nexty = nowy - wendu[right].first; if (nextx / nexty - T > eps) { nowx = nextx; nowy = nexty; right--; } else { anser = nowy - (nowx - 1.0 * T * nowy) / (wendu[right].second - T); printf("%.7f ", anser); return 0; } } if (flag) { printf("%.7f ", nowy); } } else { while (fabs(nowx / nowy - T) > eps) { if (wendu[left].second >= T) { flag = 0; break; } double nextx, nexty; nextx = nowx - 1.0 * wendu[left].first * wendu[left].second; nexty = nowy - wendu[left].first; if (nextx / nexty - T < eps) { nowx = nextx; nowy = nexty; left++; } else { anser = nowy - (1.0 * T * nowy - nowx) / (T - wendu[left].second); printf("%.7f ", anser); return 0; } } if (flag) { printf("%.7f ", nowy); } } if (!flag) { cout << 0 << endl; } return 0; }
F
给你一个三行的M列的矩阵(M<=1e18) 有N个障碍 要求从(2,1)开始到(2,M)结束 有多少种方法%MOD
先把矩阵离散化为2*N+1个矩阵 然后分情况用矩阵快速幂算答案
#include <bits/stdc++.h> #define PI acos(-1.0) #define mem(a,b) memset((a),b,sizeof(a)) #define TS printf("!!! ") #define pb push_back #define inf 1e9 //std::ios::sync_with_stdio(false); using namespace std; //priority_queue<int,vector<int>,greater<int>> que; get min const double eps = 1.0e-10; const double EPS = 1.0e-4; typedef pair<int, int> pairint; typedef long long ll; typedef unsigned long long ull; //const int maxn = 3e5 + 10; const int turn[4][2] = {{1, 0}, { -1, 0}, {0, 1}, {0, -1}}; //priority_queue<int, vector<int>, less<int>> que; //next_permutation ll Mod = 1000000007; class Matrix//定义一个矩阵结构体 { public: ll M[3][3]; clear() { mem(M, 0); } init() { clear(); for (int i = 0; i < 3; i++) { M[i][i] = 1; } } Matrix()//初始化 { mem(M, 0); } Matrix(ll Arr[3][3])//用数组来初始化 { for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) { M[i][j] = Arr[i][j]; } } }; Matrix operator * (Matrix A, Matrix B) //重载乘法运算符 { Matrix Ans; Ans.clear(); for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) for (int k = 0; k < 3; k++) { Ans.M[i][j] = (Ans.M[i][j] + 1LL * A.M[i][k] * B.M[k][j] % Mod) % Mod; } return Ans; } Matrix MFPOW(Matrix now, ll n) { Matrix x; x.init(); while (n) { if (n & 1) { x = x * now; } now = now * now; n >>= 1ll; } return x; } void print(Matrix x) { for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { cout << x.M[i][j] << " "; } cout << endl; } } struct block { ll where, from, to; }; ll a[3][3] = {{0, 1, 0}, {0, 0, 0}, {0, 0, 0}}; ll b[3][3] = {{1, 1, 0}, {1, 1, 1}, {0, 1, 1}}; ll m; block now[100005]; ll num[100005]; int judge[5][100005]; int check[5]; int pop = 1; int cnt = 1; int main() { //freopen("sample.txt", "w", stdout); int n; cin >> n; cin >> m; ll from, to, where; num[pop++] = 1, num[pop++] = m; for (int i = 1; i <= n; i++) { scanf("%lld %lld %lld", &where, &from, &to); num[pop++] = from - 1, num[pop++] = to; //将边界输入以便离散化 注意:如果L要减1以防出现错误 now[i].where = where, now[i].from = from, now[i].to = to; } sort(num + 1, num + pop); int len = unique(num + 1, num + pop) - num - 1;//因为数列是从下标1开始的所以还要再减去1 for (int i = 1; i <= n; i++) { int L = lower_bound(num + 1, num + len + 1, now[i].from) - num; int R = lower_bound(num + 1, num + len + 1, now[i].to) - num; judge[now[i].where][L]++; judge[now[i].where][R + 1]--; //因为要用到前缀和来维护每一块的第now[i].where行是否有障碍 所以要[R+1]-- } Matrix ans(a); Matrix B(b); for (int i = 2; i <= len; i++) { ll lenth = num[i] - num[i - 1]; //cout << lenth << endl; Matrix cur(b); for (int j = 1; j <= 3; j++) { check[j] += judge[j][i]; if (check[j]) { cur.M[0][j - 1] = cur.M[1][j - 1] = cur.M[2][j - 1] = 0; } } //print(cur); cur = MFPOW(cur, lenth); //print(cur); ans = ans * cur; //print(ans); } cout << ans.M[0][1] << endl; return 0; }
G
给你一个N位数的数列代表城墙 每一个城墙上面初始有A[i]个弓箭手 给你一个R 弓箭手可以防守[i-R,i+R]的地方
再给你K(K<=1e18)个弓箭手 问你每个城墙能被防守的最大最小值为多少
先前缀和处理出原始的防守值 然后二分答案用前缀和check是否能满足
#include <bits/stdc++.h> #define PI acos(-1.0) #define mem(a,b) memset((a),b,sizeof(a)) #define TS printf("!!! ") #define pb push_back #define inf 1e9 //std::ios::sync_with_stdio(false); using namespace std; //priority_queue<int,vector<int>,greater<int>> que; get min const double eps = 1.0e-10; const double EPS = 1.0e-4; typedef pair<int, int> pairint; typedef long long ll; typedef unsigned long long ull; //const int maxn = 3e5 + 10; const int maxm = 300; const int turn[4][2] = {{1, 0}, { -1, 0}, {0, 1}, {0, -1}}; //priority_queue<int, vector<int>, less<int>> que; //next_permutation ll pre[500005]; ll judgepre[500005]; int n, r; ll k; bool judge(ll x) { mem(judgepre, 0); ll remain = k; ll need; ll now = 0; for (int i = 1; i <= n; i++) { now += judgepre[i]; if (pre[i] + now < x) { need = x - pre[i] - now; remain -= need; if (remain < 0) { return false; } judgepre[i + 1] += need; if (i + 2 * r + 1 <= n) { judgepre[i + 2 * r + 1] -= need; } } } return true; } int main() { cin >> n >> r >> k; ll now; for (int i = 1; i <= n; i++) { scanf("%lld", &now); pre[max(1, i - r)] += now; if (i + r + 1 <= n) { pre[i + r + 1] -= now; } } for (int i = 1; i <= n; i++) { pre[i] = pre[i] + pre[i - 1]; } // for(int i=1;i<=n;i++) // cout<<pre[i]<<" "; // cout<<endl; ll l = 0, r = 2e18 + 2e9; ll mid; ll anser; while (l <= r) { mid = (l + r) >> 1; if (judge(mid)) { anser = mid; l = mid + 1; } else { r = mid - 1; } } cout << anser << endl; }