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("!!!\n")

#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 = ;

const int turn[][] = {{, }, { -, }, {, }, {, -}};

const int turn2[][] = {{, }, { -, }, {, }, {, -}, {, -}, { -, -}, {, }, { -, }};

//priority_queue<int, vector<int>, less<int>> que;

//next_permutation

string a;

vector<int> gra[];

int from, to;

int anser;

int n, m, s, t;

int sum;

int tong[][];

int sdis[];

int tdis[];

void getsdis()

{

        for (int i = ; 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 = ; i < len; i++)

                {

                        int to = gra[now][i];

                        if (sdis[to] > sdis[now] + )

                        {

                                sdis[to] = sdis[now] + ;

                                que.push(to);

                        }

                }

        }

}

void gettdis()

{

        for (int i = ; 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 = ; i < len; i++)

                {

                        int to = gra[now][i];

                        if (tdis[to] > tdis[now] + )

                        {

                                tdis[to] = tdis[now] + ;

                                que.push(to);

                        }

                }

        }

}

int main()

{

        cin >> n >> m >> s >> t;

        for (int i = ; i <= m; i++)

        {

                scanf("%d %d", &from, &to);

                gra[from].pb(to);

                gra[to].pb(from);

                tong[from][to] = tong[to][from] = ;

        }

        sum = (n - ) * n / ;

        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 = ; i <= n - ; i++)

        {

                for (int j = i + ; j <= n; j++)

                {

                        if (tong[i][j])

                        {

                                continue;

                        }

                        if (sdis[i] + tdis[j] +  >= mindis && sdis[j] + tdis[i] +  >= mindis)

                        {

                                anser++;

                        }

                }

        }

        cout << anser << endl;

        return ;

}

E

给你N个水管 每个水管流出的水的温度是恒定的 但是流量是可控的 给你一个温度T问你每秒最多的流量是多少

按每个水管的温度排序 然后贪心

#include <bits/stdc++.h>

#define PI acos(-1.0)

#define mem(a,b) memset((a),b,sizeof(a))

#define TS printf("!!!\n")

#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 = ;

const int turn[][] = {{, }, { -, }, {, }, {, -}};

const int turn2[][] = {{, }, { -, }, {, }, {, -}, {, -}, { -, -}, {, }, { -, }};

//priority_queue<int, vector<int>, less<int>> que;

//next_permutation

//double a[200005];

//double t[200005];

pair<double, double> wendu[];

int n;

double T;

double anser;

int flag = ;

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 = ; i <= n; i++)

        {

                scanf("%lf", &wendu[i].first);

        }

        for (int i = ; i <= n; i++)

        {

                scanf("%lf", &wendu[i].second);

        }

        sort(wendu + , wendu +  + n, cmp);

        int left = ;

        int right = n;

        for (int i = ; i <= n; i++)

        {

                nowx += 1.0 * wendu[i].first * wendu[i].second;

                nowy += wendu[i].first;

        }

        //printf("%.8f\n", nowx);

        //printf("%.8f\n", nowy);

        if (fabs(nowx / nowy - T) < eps)

        {

                printf("%.7f\n", nowy);

                return ;

        }

        else if (nowx / nowy - T > eps)

        {

                while (fabs(nowx / nowy - T) > eps)

                {

                        if (wendu[right].second <= T)

                        {

                                flag = ;

                                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\n", anser);

                                return ;

                        }

                }

                if (flag)

                {

                        printf("%.7f\n", nowy);

                }

        }

        else

        {

                while (fabs(nowx / nowy - T) > eps)

                {

                        if (wendu[left].second >= T)

                        {

                                flag = ;

                                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\n", anser);

                                return ;

                        }

                }

                if (flag)

                {

                        printf("%.7f\n", nowy);

                }

        }

        if (!flag)

        {

                cout <<  << endl;

        }

        return ;

}

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("!!!\n")

#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[][] = {{, }, { -, }, {, }, {, -}};

//priority_queue<int, vector<int>, less<int>> que;

//next_permutation

ll Mod = ;

class Matrix//定义一个矩阵结构体

{

public:

        ll M[][];

        clear()

        {

                mem(M, );

        }

        init()

        {

                clear();

                for (int i = ; i < ; i++)

                {

                        M[i][i] = ;

                }

        }

        Matrix()//初始化

        {

                mem(M, );

        }

        Matrix(ll Arr[][])//用数组来初始化

        {

                for (int i = ; i < ; i++)

                        for (int j = ; j < ; j++)

                        {

                                M[i][j] = Arr[i][j];

                        }

        }

};

Matrix operator * (Matrix A, Matrix B) //重载乘法运算符

{

        Matrix Ans;

        Ans.clear();

        for (int i = ; i < ; i++)

                for (int j = ; j < ; j++)

                        for (int k = ; k < ; 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 & )

                {

                        x = x * now;

                }

                now = now * now;

                n >>= 1ll;

        }

        return x;

}

void print(Matrix x)

{

        for (int i = ; i < ; i++)

        {

                for (int j = ; j < ; j++)

                {

                        cout << x.M[i][j] << " ";

                }

                cout << endl;

        }

}

struct block

{

        ll where, from, to;

};

ll a[][] = {{, , }, {, , }, {, , }};

ll b[][] = {{, , }, {, , }, {, , }};

ll m;

block now[];

ll num[];

int judge[][];

int check[];

int pop = ;

int cnt = ;

int main()

{

        //freopen("sample.txt", "w", stdout);

        int n;

        cin >> n;

        cin >> m;

        ll from, to, where;

        num[pop++] = , num[pop++] = m;

        for (int i = ; i <= n; i++)

        {

                scanf("%lld %lld %lld", &where, &from, &to);

                num[pop++] = from - , num[pop++] = to; //将边界输入以便离散化 注意:如果L要减1以防出现错误

                now[i].where = where, now[i].from = from, now[i].to = to;

        }

        sort(num + , num + pop);

        int len = unique(num + , num + pop) - num - ;//因为数列是从下标1开始的所以还要再减去1

        for (int i = ; i <= n; i++)

        {

                int L = lower_bound(num + , num + len + , now[i].from) - num;

                int R = lower_bound(num + , num + len + , now[i].to) - num;

                judge[now[i].where][L]++;

                judge[now[i].where][R + ]--; //因为要用到前缀和来维护每一块的第now[i].where行是否有障碍 所以要[R+1]--

        }

        Matrix ans(a);

        Matrix B(b);

        for (int i = ; i <= len; i++)

        {

                ll lenth = num[i] - num[i - ];

                //cout << lenth << endl;

                Matrix cur(b);

                for (int j = ; j <= ; j++)

                {

                        check[j] += judge[j][i];

                        if (check[j])

                        {

                                cur.M[][j - ] = cur.M[][j - ] = cur.M[][j - ] = ;

                        }

                }

                //print(cur);

                cur = MFPOW(cur, lenth);

                //print(cur);

                ans = ans * cur;

                //print(ans);

        }

        cout << ans.M[][] << endl;

        return ;

}

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("!!!\n")

#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 = ;

const int turn[][] = {{, }, { -, }, {, }, {, -}};

//priority_queue<int, vector<int>, less<int>> que;

//next_permutation

ll pre[];

ll judgepre[];

int n, r;

ll k;

bool judge(ll x)

{

        mem(judgepre, );

        ll remain = k;

        ll need;

        ll now = ;

        for (int i = ; i <= n; i++)

        {

                now += judgepre[i];

                if (pre[i] + now < x)

                {

                        need = x - pre[i] - now;

                        remain -= need;

                        if (remain < )

                        {

                                return false;

                        }

                        judgepre[i + ] += need;

                        if (i +  * r +  <= n)

                        {

                                judgepre[i +  * r + ] -= need;

                        }

                }

        }

        return true;

}

int main()

{

        cin >> n >> r >> k;

        ll now;

        for (int i = ; i <= n; i++)

        {

                scanf("%lld", &now);

                pre[max(, i - r)] += now;

                if (i + r +  <= n)

                {

                        pre[i + r + ] -= now;

                }

        }

        for (int i = ; i <= n; i++)

        {

                pre[i] = pre[i] + pre[i - ];

        }

        //        for(int i=1;i<=n;i++)

        //        cout<<pre[i]<<" ";

        //        cout<<endl;

        ll l = , r = 2e18 + 2e9;

        ll mid;

        ll anser;

        while (l <= r)

        {

                mid = (l + r) >> ;

                if (judge(mid))

                {

                        anser = mid;

                        l = mid + ;

                }

                else

                {

                        r = mid - ;

                }

        }

        cout << anser << endl;

}

最新文章

  1. DAO层，Service层，Controller层、View层 的分工合作
  2. [LeetCode] Mini Parser 迷你解析器
  3. bak骗子公司
  4. Android Studio 个人常用设置
  5. 接口测试总结&lt;转&gt;
  6. ASP.NET Web API的安全管道
  7. 关闭linux centos各种声音
  8. Synchronized Methods
  9. Mozilla公布WebVR API标准草案
  10. nmon命令用法
  11. foreach笔记
  12. 访问servlet的路径问题
  13. 老男孩Python全栈开发（92天全）视频教程 自学笔记05
  14. jQuery上下滑动内容切换选项卡
  15. webpack 样式表抽离成专门的单独文件并且设置版本号
  16. margin的垂直方向塌陷
  17. 20165213 Exp4 恶意代码分析
  18. NOIP刷题建议（未完结）
  19. 适用于WebApi的SQL注入过滤器
  20. Unix/Linux系统中僵尸进程是如何产生的？有什么危害？如何避免？

热门文章

  1. mysql 5.7 安装配置及无法启动的问题解决
  2. .net framework4.6项目的dll升级后，未找到方法“System.String.GetPathsOfAllDirectoriesAbove”解决
  3. 惠普DL360G6安装ESXi主机后设置多块网卡
  4. 方法二破解：Excel工作表保护密码
  5. Spring 缓存注解解析过程
  6. BDD Cucumber 实战
  7. babel-node 和 nodemon
  8. vs2010 setup 打包 安装 BAT批处理实现自动安装软件功能
  9. CentOS7_装机软件推荐
  10. .Net 逆向 Reflector之reflexil使用