GVKun编程网logo

CodeForces - 954D Fight Against Traffic

18

对于CodeForces-954DFightAgainstTraffic感兴趣的读者，本文将提供您所需要的所有信息，并且为您提供关于CGAffineTransformMakeTranslation和C

对于CodeForces - 954D Fight Against Traffic感兴趣的读者，本文将提供您所需要的所有信息，并且为您提供关于CGAffineTransformMakeTranslation和CGAffineTransform、Codeforces - 102222H - Fight Against Monsters - 贪心、Codeforces - 1194D - 1-2-K Game - dp、CodeForces - Duff and Weight Lifting - [I/O加速]的宝贵知识。

本文目录一览：

CodeForces - 954D Fight Against Traffic

CodeForces - 954D Fight Against Traffic

fight Against Traffic

Little town Nsk consists of n junctions connected by m bidirectional roads. Each road connects two distinct junctions and no two roads connect the same pair of junctions. It is possible to get from any junction to any other junction by these roads. The distance between two junctions is equal to the minimum possible number of roads on a path between them.

In order to improve the transportation system,the city council asks mayor to build one new road. The problem is that the mayor has just bought a wonderful new car and he really enjoys a ride from his home,located near junction s to work located near junction t. Thus,he wants to build a new road in such a way that the distance between these two junctions won‘t decrease.

You are assigned a task to compute the number of pairs of junctions that are not connected by the road,such that if the new road between these two junctions is built the distance between s and t won‘t decrease.

Input

The firt line of the input contains integers n, m, s and t (2?≤?n?≤?1000, 1?≤?m?≤?1000, 1?≤?s,?t?≤?n, s?≠?t) — the number of junctions and the number of roads in Nsk,as well as the indices of junctions where mayors home and work are located respectively. The i-th of the following m lines contains two integers ui and vi (1?≤?ui,?vi?≤?n, ui?≠?vi),meaning that this road connects junctions ui and vi directly. It is guaranteed that there is a path between any two junctions and no two roads connect the same pair of junctions.

Output

Print one integer — the number of pairs of junctions not connected by a direct road,such that building a road between these two junctions won‘t decrease the distance between junctions s and t.

Examples

Input 
5 4 1 5
1 2
2 3
3 4
4 5
Output 
0
Input 
5 4 3 5
1 2
2 3
3 4
4 5
Output 
5
Input 
5 6 1 5
1 2
1 3
1 4
4 5
3 5
2 5
Output 
3

题意:n个城镇，m条道路(无向 s(起点 t(终点 然后求建一条新路，s-t的最短路径不会改变。
思路:跑两次spfa s到各个点的最短路 t到各个点的最短路 然后枚举每次没有路的点 然后判断dis1[i]+dis2[j]+1>=dis1[t]&&dis1[j]+dis2[i]+1>=dis1[t]，这样就cnt++

分享图片

分享图片

#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn= 1000+5;
const int INF = 0x3f3f3f3f;
int dis1[maxn],dis2[maxn];
int d[maxn][maxn],n,m;
bool vis[maxn];
void spfa(int s,int dis[1005])
{
    queue<int> q;
    memset(vis,0,sizeof(vis));
    vis[s]=1;
    dis[s]=0;
    q.push(s);
    while(!q.empty())
    {
        int v=q.front();
        q.pop();
        vis[v]=0;
        for(int i=1; i<=n; i++)
        {
            int w=d[v][i];
            if(w==INF)
                continue;
            if(dis[i]>dis[v]+w)
            {
                dis[i]=dis[v]+w;
                if(!vis[i])
                {
                    q.push(i);
                    vis[i]=1;
                }
            }
        }

    }

}
int main()
{
    int s,t,u,v;
    scanf("%d %d %d %d",&n,&m,&s,&t);
    memset(d,INF,sizeof(d));
    memset(dis1,sizeof(dis1));
    memset(dis2,sizeof(dis2));
    for(int i=1; i<=m; i++)
    {
        scanf("%d %d",&u,&v);
        d[u][v]=d[v][u]=1;
    }

    spfa(s,dis1);
    spfa(t,dis2);
    int cnt=0;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n&&i!=j; j++)
        {
            if(i==t&&j==s)
                continue;
            if((dis1[i]+dis2[j]+1>=dis1[t])&&(dis1[j]+1+dis2[i]>=dis1[t])&&d[i][j]==INF)
            {
                cnt++;
            }
        }
    cout<<cnt<<endl;

}
View Code

 

 

 

PS：摸鱼怪的博客分享，欢迎感谢各路大牛的指点~

CGAffineTransformMakeTranslation和CGAffineTransform

CGAffineTransformMakeTranslation和CGAffineTransform

1.CGAffineTransformMakeTranslation每次都是以最初位置的中心点为起始参照

   CGAffineTransformTranslate每次都是以传入的transform为起始参照

   CGAffineTransformIdentity为最初状态，即最初位置的中心点

2.3个按钮，bt1，bt2，bt3，bt1和bt2控制bt3的移动

- (IBAction)bt1clicked:(id)sender {

    self.bt3.transform = CGAffineTransformMakeTranslation(10, 0);

}

- (IBAction)bt2clicked:(id)sender {

    ／／self.bt3.transform = CGAffineTransformTranslate(CGAffineTransformIdentity, 10, 0);

    self.bt3.transform = CGAffineTransformTranslate(self.bt3.transform, 10, 0);

}

点击bt1，第一次移动10个像素，以后都是以最初位置的中心点为起始参照，所以后续bt1无论点击多少次，按钮都在初始位置偏移10个像素的位置不动

点击bt1一次，再点击bt2一次，偏移20像素，点击bt2时，上一次按钮点击的偏移作为这次的参照

只点击bt2一次，偏移10个像素

不断点击bt2，bt3不断偏移10个像素


bt2clicked的第一句不注释：

第一次点击bt2，bt3偏移20，后续再点击，永远再第一次点击后的位置，再点击bt1，回到初始偏移10的位置（往回走了10）

点击bt1，偏移10，再点击bt2，在bt1点击基础上再偏移10，后续再点击不动（ CGAffineTransformTranslate(CGAffineTransformIdentity, 10, 0);每次都是从最初位置开始偏移）


Codeforces - 102222H - Fight Against Monsters - 贪心

Codeforces - 102222H - Fight Against Monsters - 贪心

https://codeforc.es/gym/102222/problem/H 题意：有一堆怪兽，怪兽有 HP 和 ATK。你有一个英雄，英雄每次先被所有怪兽打，然后打其中一个怪兽。打的伤害递增，第一次 1，第二次 2，以此类推。 为什么感觉是贪心呢？证明一波。

首先开始打一个怪兽肯定一直打到死为止。那么打死他要求的次数可以二分出来（其实暴力也可以）。两只怪兽交换打的顺序会不会变好？

先打第一只怪兽： $num_1sumatk+num_2(sumatk-atk_1)$

先打第二只怪兽： $num_2sumatk+num_1(sumatk-atk_2)$

那么什么情况下先打第二只会更好呢？当然是上式大于下式： $num_1sumatk+num_2(sumatk-atk_1)>num_2sumatk+num_1(sumatk-atk_2)$

化简： $num_1atk_2>num_2atk_1$

当上式成立时需要交换。

插进优先队列里面一搞，又不会爆 longlong。一波搞定。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int read() {
    int x=0;
    int f=0;
    char c;
    do {
        c=getchar();
        if(c==''-'')
            f=1;
    } while(c<''0''||c>''9'');
    do {
        x=(x<<3)+(x<<1)+c-''0'';
        c=getchar();
    } while(c>=''0''&&c<=''9'');
    return f?-x:x;
}

inline void _write(int x) {
    if(x>9)
        _write(x/10);
    putchar(x%10+''0'');
}

inline void write(int x) {
    if(x<0) {
        putchar(''-'');
        x=-x;
    }
    _write(x);
    putchar(''\n'');
}

void TestCase(int ti);

int main() {
#ifdef Yinku
    freopen("Yinku.in","r",stdin);
    //freopen("Yinku.out","w",stdout);
#endif // Yinku
    int T=read();
    for(int ti=1;ti<=T;ti++)
        TestCase(ti);
}

/*---  ---*/

inline int s1(int x){
    return ((x+1)*x)>>1;
}

struct Monster{
    int hp;
    int atk;
    int num;
    inline void calc(){
        int l=1,r=1000,m;
        while(1){
            m=l+r>>1;
            if(m==l){
                int s=s1(l);
                if(s>=hp){
                    num=l;
                    return;
                }
                else{
                    num=r;
                    return;
                }
            }
            int s=s1(m);
            if(s==hp){
                num=m;
                return;
            }
            else if(s<hp)
                l=m+1;
            else
                r=m;
        }
    }

    inline bool operator<(const Monster &m)const{
        return !(atk*m.num>=m.atk*num);
    }
}monster;

priority_queue<Monster> pq;

void TestCase(int ti) {
    ll sumatk=0;
    int n=read();
    for(int i=1;i<=n;i++){
        monster.hp=read();
        monster.atk=read();
        sumatk+=monster.atk;
        monster.calc();
        pq.push(monster);
    }
    ll sumdamage=0;
    while(!pq.empty()){
        monster=pq.top();
        pq.pop();
        sumdamage+=sumatk*monster.num;
        sumatk-=monster.atk;
    }
    printf("Case #%d: %lld\n",ti,sumdamage);
}

Codeforces - 1194D - 1-2-K Game - dp

Codeforces - 1194D - 1-2-K Game - dp

https://codeforc.es/contest/1194/problem/D 打个 n=30 的表好像看出了规律。

其实假设 k==3，那么

sg[0]=0, sg[1]=mex{sg[0]}=1, sg[2]=mex{sg[0],sg[1]}=2, sg[3]=mex{sg[0],sg[1],sg[2]}=3, sg[4]=mex{sg[1],sg[2],sg[3]}=0, sg[5]=mex{sg[2],sg[3],sg[4]}=1, sg[6]=mex{sg[3],sg[4],sg[5]}=2, sg[7]=mex{sg[4],sg[5],sg[6]}=3, sg[8]=mex{sg[5],sg[6],sg[7]}=0.

也不太清楚 sg 函数的具体意义是什么。不过可以看出规律。其实大概可以猜出来就是 0,1,2,3 循环。策略就是一开始先手是 4 倍数必败的，无论先手选什么，后手总可以掏出一个数使它凑出一个 4。一直到 0，而模 4 余非零数的话就相当于出让先手。

再假设 k==4，那么

sg[0]=0, sg[1]=mex{sg[0]}=1, sg[2]=mex{sg[0],sg[1]}=2, sg[3]=mex{sg[1],sg[2]}=0, sg[4]=mex{sg[0],sg[2],sg[3]}=1, sg[5]=mex{sg[1],sg[3],sg[4]}=2, sg[6]=mex{sg[2],sg[4],sg[5]}=0, sg[7]=mex{sg[3],sg[5],sg[6]}=1, sg[8]=mex{sg[4],sg[6],sg[7]}=2.

又可以看出规律。可以归纳出来就是 0,1,2 循环。策略就是一开始先手是 3 倍数必败的，无论先手选什么，后手总可以掏出一个数使它凑出一个 3 或者 6。一直到 0，而模 3 余非零数的话就相当于出让先手。

然后解法就很好理解了，可以 dp 算出小数据的时候的分布情况，总能找到一些必胜状态，而这个时候就很玄学了。当 k 不是 3 的倍数的时候。无论是选 1,2 还是 k，都有办法凑一个数变成 3 的倍数。所以必败状态的点再加若干个 3 的倍数也是必败。？？？

管他什么东西呢反正 sg 函数有规律。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

//bool dp[1005];

int main() {
#ifdef Yinku
    freopen("Yinku.in", "r", stdin);
    //freopen("Yinku.out", "w", stdout);
#endif // Yinku
    //dp[0]=0;
    //dp[i]=1,when dp[i-1]=0||dp[i-2]=0||dp[i-k]=0,else 0
    int q;
    while(~scanf("%d", &q)) {
        while(q--) {
            int n, k;
            scanf("%d%d", &n, &k);
//            dp[0] = 0;
//            for(int i = 1; i <= n; i++) {
//                dp[i] = 0;
//                if(i - 1 >= 0)
//                    dp[i] |= !dp[i - 1];
//                if(i - 2 >= 0)
//                    dp[i] |= !dp[i - 2];
//                if(i - k >= 0)
//                    dp[i] |= !dp[i - k];
//            }
//            for(int i = 0; i <= n; i++) {
//                printf("%2d ", i);
//            }
//            printf("\n");
//            for(int i = 0; i <= n; i++) {
//                printf("%2d ", dp[i]);
//            }
//            printf("\n");

            bool BobWin=true;
            if(k%3==0){
                n%=(k+1);
                if(n%3)
                    BobWin=false;
                if(n==k)
                    BobWin=false;
            }
            else{
                if(n%3)
                    BobWin=false;
            }

            puts(BobWin?"Bob":"Alice");
        }
    }
}

CodeForces - Duff and Weight Lifting - [I/O加速]

CodeForces - Duff and Weight Lifting - [I/O加速]

CodeForces - Duff and Weight Lifting - #326 (Div. 1)

c++ iostream I/O优化

http://codeforces.com/contest...

一句话题意：有若干个数字，都是2的n次幂；每次取出若干个数字，且要保证取出的数字之和也是2的n次幂；问至少要取多少次。

样例输入：
5
1 1 2 3 3

样例输出：
2

解：

我们从最简单的样例入手。

样例输入可以整理如下。x的后面表示这个数字的出现次数。

2^1 x2
2^2 x1
2^3 x2

我们发现，两个相同幂次的数，刚好能“等价变换”为更高次的数。

2^1 x2 => 2^2 x1

再加上已有的2^2，总共有2个2^2啦。于是，继续变换，

2^2 x2 => 2^3 x1

再加上已有的2个2^3，就有3个2^3啦。

2^3 x2+1

取出其中两个进行“变换”，最终结果就是

2^3 x1
2^4 x1

然后，我们发现不管怎么操作都无法进一步组合两个数进行变换。现在有两个数，所以答案是2。

做到这里，就不难看出其中的规律。二进制下的“进位”而已。

#include <cstdio>
#include<cmath>
#include<iostream>
using namespace std;

int orz[1000000+10000];
int l[] ={1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576};
int search(int n){
    for(int i = 0;i<20;i++){
        if(l[i+1]>=n){
            return i;
        }
    }
    return -1;
}
int main(){
    std::ios::sync_with_stdio(false);  
    std::cin.tie(0);  
    int n,t;
    scanf("%d", &n);
    int step = 0;
    int max = 0;
    for(int i = 0;i<n;i++){
        scanf("%d", &t);
        max = (t>max?t:max);
        orz[t]++;
    }
    for(int i = 0;i<=max;i++){
        if(orz[i] == 0) continue;
        int now_cnt = orz[i];
        int pow;
        while(now_cnt){
            if(now_cnt == 1) step++;
            now_cnt -= l[pow = log2(now_cnt)];
            orz[max=(i+pow>max?i+pow:max),i+pow]++;
        }
    }
    printf("%d\n", step);
    return 0;
}

其中两行，

std::ios::sync_with_stdio(false);  
std::cin.tie(0);

就是所谓的iostream优化。

第一行的原理就是解除iostream和stdio的绑定。

第二行的原理是解除cin与cout的绑定。

详情请看这篇文章。

为啥要优化呢？因为我起初做这题是用的51nod（这个网站提供这题的中文题目）的机器非常辣鸡，就是卡I/O。疯狂TLE。

我试了能AC的两种方法，第一种是删除所有c++特性语句，使用printf与scanf，用c来提交；第二种就是所述的iostream优化。

题外话：

有些时候，自己重写printf和scanf效率更高。

因为getchar和putchar函数很快。

从qscqesze的岛娘模版上摘抄如下：

template<class T> inline T& RD(T &x){  
    //cin >> x;  
    //scanf("%d", &x);  
    char c; for (c = getchar(); c < ''0''; c = getchar()); x = c - ''0''; for (c = getchar(); ''0'' <= c && c <= ''9''; c = getchar()) x = x * 10 + c - ''0'';  
    //char c; c = getchar(); x = c - ''0''; for (c = getchar(); c >= ''0''; c = getchar()) x = x * 10 + c - ''0'';  
    return x;  
}  
  
int ____Case; template<class T> inline void OT(const T &x){  
    //if (x == -1) printf("Case %d: NO\n", ++____Case);  
    //else printf("Case %d: %d\n", ++____Case, x);  
    //printf("%I64d\n", x);  
    //printf("%.2lf\n", x);  
    printf("%d\n", x);  
    //cout << x << endl;  
}

这相当于重写了scanf。

至于用putchar重写printf……以后再说吧，因为很少遇到大量输出的情况。

关于CodeForces - 954D Fight Against Traffic的介绍现已完结，谢谢您的耐心阅读，如果想了解更多关于CGAffineTransformMakeTranslation和CGAffineTransform、Codeforces - 102222H - Fight Against Monsters - 贪心、Codeforces - 1194D - 1-2-K Game - dp、CodeForces - Duff and Weight Lifting - [I/O加速]的相关知识，请在本站寻找。

本文标签：

上一篇1018 Public Bike Management (30)（30 分）

下一篇BI Publiser bursting 邮件附件名称乱码问题（邮件附件文件名乱码）

相关文章