2019年3月

http://poj.org/problem?id=2236
关键点在于用并查集实现两个网络是否连通的查询
每次在修过的电脑的时候把每台电脑路径小于d的都合并一遍 这样子查询就方便了。

#include <iostream>
#include <math.h>
using namespace std; 
int n;
double d;
struct{
    int x,y;
}arr[1005];
int f[1005];
bool repair[1005];
int find(int x){
    if(f[x] == x){
        return x;
    }else{
        return f[x] = find(f[x]);
    }
}
void merge(int x,int y){
    int a = find(x);
    int b = find(y);
    if(a == b){
        return;
    }
    f[b] = a;
}

double dis(int a,int b){
    int x1 = arr[a].x;
    int y1 = arr[a].y;
    int x2 = arr[b].x;
    int y2 = arr[b].y;
    return sqrt(double(pow(x1-x2, 2) + pow(y1-y2, 2)));
}
int main(int argc, char** argv) {
    cin >> n >> d;
    for(int i = 1; i<=n; i++){
        cin >> arr[i].x >> arr[i].y;
        f[i] = i;
    }
    char c;
    while(cin >> c){
        if(c == 'O'){
            int j;
            cin >> j;
            repair[j] = true;
            for(int i = 1; i<=n; i++){
                if(i == j){
                    continue;
                }
                if(!repair[i]){
                    continue;
                }
                if(dis(i, j) > d){
                    continue;
                }
                merge(i, j);
            }
        }else if(c == 'S'){
            int a,b;
            cin >> a >> b;
            if(find(a) == find(b)){
                cout << "SUCCESS" << endl;
            }else{
                cout << "FAIL" << endl;
            }
        }
    }
    return 0;
}

C国由n个小岛组成,为了方便小岛之间联络,C国在小岛间建立了m座大桥,每座大桥连接两座小岛。两个小岛间可能存在多座桥连接。然而,由于海水冲刷,有一些大桥面临着不能使用的危险。
如果两个小岛间的所有大桥都不能使用,则这两座小岛就不能直接到达了。然而,只要这两座小岛的居民能通过其他的桥或者其他的小岛互相到达,他们就会安然无事。但是,如果前一天两个小岛之间还有方法可以到达,后一天却不能到达了,居民们就会一起抗议。
现在C国的国王已经知道了每座桥能使用的天数,超过这个天数就不能使用了。现在他想知道居民们会有多少天进行抗议。

样例说明
  第一天后2和3之间的桥不能使用,不影响。
  第二天后1和2之间,以及1和3之间的桥不能使用,居民们会抗议。
  第三天后3和4之间的桥不能使用,居民们会抗议。

数据规模和约定
  对于30%的数据,1<=n<=20,1<=m<=100;
  对于50%的数据,1<=n<=500,1<=m<=10000;
  对于100%的数据,1<=n<=10000,1<=m<=100000,1<=a, b<=n, 1<=t<=100000。

输入格式:
输入的第一行包含两个整数n, m,分别表示小岛的个数和桥的数量。
接下来m行,每行三个整数a, b, t,分别表示该座桥连接a号和b号两个小岛,能使用t天。小岛的编号从1开始递增。

输出格式:
输出一个整数,表示居民们会抗议的天数。

输入样例:
在这里给出一组输入。例如:

4 4
1 2 2
1 3 2
2 3 1
3 4 3
输出样例:
在这里给出相应的输出。例如:

2
关键点:
这题关键点在于 是连通点的消失 所以我们可以用一个并查集来负责对点进行合并、但是如果正着来每次都要查询连通点总数是否有变化会很慢 所以可以逆向来 把点一个个加上去 则只需要修改merge函数 如果新增点则cnt[天数]= 1
最后统计的时候把cnt数组求和即可

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int n,m;
struct d{
    int a,b,t;
}arr[100005];
int cnt[100005],rmax,f[10005];
int find(int x){
    if(f[x] == x){
        return x;
    }else{
        return f[x] = find(f[x]);
    }
}
void merge(d x){
    int a = find(x.a);
    int b = find(x.b);
    if(a == b){
        return;
    }
    f[b] = a;
    cnt[x.t] = 1;
}
bool cmp(d a,d b){
    return a.t > b.t;
}
int main()
{
    cin >> n >> m;
    for(int i = 1; i<=n; i++){
        f[i] = i;
    }
    for(int i = 1; i<=m; i++){
        cin >> arr[i].a >> arr[i].b >> arr[i].t;
        rmax = max(rmax, arr[i].t); 
    }
    sort(arr+1, arr+1+m, cmp);
    for(int i = 1; i<=m; i++){
        merge(arr[i]);
    }
    int res = 0;
    for(int i = 1; i<=rmax; i++){
        res += cnt[i];
    }
    cout << res << endl;
    return 0;
}

栋栋正在和同学们玩一个数字游戏。

游戏的规则是这样的:栋栋和同学们一共n个人围坐在一圈。栋栋首先说出数字1。接下来,坐在栋栋左手边的同学要说下一个数字2。再下面的一个同学要从上一个同学说的数字往下数两个数说出来,也就是说4。下一个同学要往下数三个数,说7。依次类推。

为了使数字不至于太大,栋栋和同学们约定,当在心中数到 k-1 时,下一个数字从0开始数。例如,当k=13时,栋栋和同学们报出的前几个数依次为:
  1, 2, 4, 7, 11, 3, 9, 3, 11, 7。

  游戏进行了一会儿,栋栋想知道,到目前为止,他所有说出的数字的总和是多少。

样例说明
  栋栋说出的数依次为1, 7, 9,和为17。

数据规模和约定
  1 < n,k,T < 1,000,000;

输入格式:
 输入的第一行包含三个整数 n,k,T,其中 n 和 k 的意义如上面所述,T 表示到目前为止栋栋一共说出的数字个数。

输出格式:
 输出一行,包含一个整数,表示栋栋说出所有数的和。

输入样例:
在这里给出一组输入。例如:

3 13 3
输出样例:
在这里给出相应的输出。例如:

17
关键点:
等差数列求区间和:
值=(首项+末项)*项数/2
更新首项:l=1+in; 末项:r=n+in;
所有数据类型long long

#include<stdio.h>
int main()
{
    long long n,k,t;
    while(~scanf("%lld%lld%lld",&n,&k,&t))
    {
        long long x=1,ans=1;
        long long l=1,r=n;
        for(int i=1; i<t; i++)
        {
            x+=(l+r)*n/2;
            x=x%k;
            ans+=x;
            l=1+i*n;
            r=n+i*n;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

有一棵二叉树,最大深度为D,且所有叶子的深度都相同。所有结点从上到下从左到右编号为1,2,3,…,2D-1。在结点1处放一个小球,它会往下落。每个内结点上都有一个开关,初始全部关闭,当每次有小球落到一个开关上时,它的状态都会改变。当小球到达一个内结点时,如果该结点上的开关关闭,则往左走,否则往右走,直到走到叶子结点,如图所示。
pimg1548_1.jpg

输入格式:
共n行(n≤1000),每行两个整数表示叶子深度D和小球个数I,D≤20。

输出格式:
每组输入对应一行输出,一个整数表示小球最后所在的叶子编号。

输入样例:
在这里给出一组输入。例如:

4 2
3 4
10 1
2 2
8 128
16 12345
输出样例:
在这里给出相应的输出。例如:

12
7
512
3
255
36358
关键点:
模拟会超时
我们以d = 4 l = 2为例子
当l为2时进入根节点会往右节点走 接着就会一直往左子树走 我们就会发现 这种情况就是 d = 3 l = 1 的情况
这样子问题就简化成了 如果当前小球编号为l 如果l%2 == 1 则当前小球走的路线跟l = l / 2 + 1 否则 就是 l = l / 2 的路线一样 就可以根据奇偶性来判定最后一个球的路线直接推出结果

#include <iostream>
#include <string>
using namespace std; 
int main(int argc, char** argv) {
    int d,l;
    while(cin >> d >> l){
        int k = 1;
        for(int i = 1; i<=d-1; i++){
            if(l % 2){
                k = k * 2;
                l = l / 2 + 1;
            }else{
                k = k * 2 + 1;
                l = l / 2;
            }
        }
        cout << k << endl;
    }
    return 0;
}

L1-048 矩阵A乘以B (15 分)
给定两个矩阵A和B,要求你计算它们的乘积矩阵AB。需要注意的是,只有规模匹配的矩阵才可以相乘。即若A有R
​a
​​ 行、C
​a
​​ 列,B有R
​b
​​ 行、C
​b
​​ 列,则只有C
​a
​​ 与R
​b
​​ 相等时,两个矩阵才能相乘。

输入格式:
输入先后给出两个矩阵A和B。对于每个矩阵,首先在一行中给出其行数R和列数C,随后R行,每行给出C个整数,以1个空格分隔,且行首尾没有多余的空格。输入保证两个矩阵的R和C都是正数,并且所有整数的绝对值不超过100。

输出格式:
若输入的两个矩阵的规模是匹配的,则按照输入的格式输出乘积矩阵AB,否则输出Error: Ca != Rb,其中Ca是A的列数,Rb是B的行数。

输入样例1:
2 3
1 2 3
4 5 6
3 4
7 8 9 0
-1 -2 -3 -4
5 6 7 8
输出样例1:
2 4
20 22 24 16
53 58 63 28
输入样例2:
3 2
38 26
43 -5
0 17
3 2
-11 57
99 68
81 72
输出样例2:
Error: 2 != 3
关键点矩阵乘法

#include <iostream>
#include <bits/stdc++.h>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int n;
long long a[1005][1005];
long long b[1005][1005];
long long c[1005][1005];
int main(int argc, char** argv) {
    long long ra,ca,rb,cb;
    cin >> ra >> ca;
    for(int i = 1; i<=ra; i++){
        for(int j = 1; j<=ca; j++){
            cin >> a[i][j];
        }
    }
    cin >> rb >> cb;
    for(int i = 1; i<=rb; i++){
        for(int j = 1; j<=cb; j++){
            cin >> b[i][j];
        }
    }
    if(ca != rb){
        printf("Error: %d != %d", ca, rb);
        return 0;
    }
    for(int i = 1; i<=ra; i++){
        for(int j = 1; j<=cb; j++){
            long long sum = 0;
            for(int k = 1; k<=ca; k++){
                sum += a[i][k] * b[k][j];
            }
            c[i][j] = sum; 
        }
    }
    cout << ra << " " << cb << endl;
    for(int i = 1; i<=ra; i++){
        for(int j = 1; j<=cb; j++){
            cout << c[i][j];
            if(j != cb){
                cout << " ";                
            }
        }
        if(i != ra){
            cout << endl;
        }
    }
    return 0;
}