ABC073

[ABC073C] Write and Erase

题面翻译

给你一个空序列，以及$N$个询问$Ai$，如在序列中有这个数，就将序列中的数删去，如在序列中没有这个数，就将这个数加入序列中，问最后序列中的元素个数为多少。

数据范围

$1≤N≤100000$，$1≤Ai≤1000000000(=10^9)$

题目描述

あなたは、joisinoお姉ちゃんと以下のようなゲームをしています。

最初、何も書いていない紙がある。

joisinoお姉ちゃんが一つの数字を言うので、その数字が紙に書いてあれば紙からその数字を消し、書いていなければその数字を紙に書く。これを $ N $ 回繰り返す。

その後、紙に書かれている数字がいくつあるかを答える。

joisinoお姉ちゃんが言った数字が、言った順番に $ A_1, ... ,A_N $ として与えられるので、ゲーム終了後に紙に書かれている数字がいくつあるか答えてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ A_1 $ $ : $ $ A_N $

输出格式

ゲーム終了後に紙に書かれている数字の個数を出力せよ。

样例 #1

样例输入 #1
3
6
2
6
样例输出 #1
1
样例 #2

样例输入 #2
4
2
5
5
2
样例输出 #2
0
样例 #3

样例输入 #3
6
12
22
16
22
18
12
样例输出 #3
2
提示

制約

$ 1≦N≦100000 $

$ 1≦A_i≦1000000000(=10^9) $

入力は全て整数である。

Sample Explanation 1

以下の操作を行うこととなります。 - 紙に $ 6 $ は書かれていないので、$ 6 $ を書く。 - 紙に $ 2 $ は書かれていないので、$ 2 $ を書く。 - 紙に $ 6 $ は書かれているので、$ 6 $ を消す。よって、最後に書いてあるのは $ 2 $ だけなので、答えは $ 1 $ です。

Sample Explanation 2

最後に紙に数字が一つも書かれていない場合もあります。

思路

直接开个桶，在线处理就行。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const double PI=acos(-1);
const int MAXN=2e5+10;
const ll mod=1e9+7;
const ll INF=1e9;
ll a[MAXN];
map<ll,int> m;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n;cin>>n;
    ll ans=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(m[a[i]]){
            ans--;
            m[a[i]]=0;
        }
        else {
            m[a[i]]++;
            ans++;
        }
    }
    cout<<ans;
    return 0;
}

[ABC073D] joisino's travel

题面翻译

一个人旅行，必须经过指定的r个城市，问最短的路程是多少。他可以从任意一个城市开始，任意一个城市结束。保证图是连通的。

题目描述

Atcoder国には $ N $ 個の町があり、$ M $ 本の双方向に移動可能な道で結ばれています。

また、 $ i $ 本目の道は町 $ A_i $ と町 $ B_i $ の間を距離 $ C_i $ で結んでいます。

joisinoお姉ちゃんは、この国の $ R $ 個の町 $ r_1,r_2..r_R $ を訪れることとなりました。

最初に訪れる町までの移動と、最後に訪れる町からの移動は空路で行うが、それ以外は道を使わなければなりません。

町を訪れる順番を、道での移動距離が最小となるように決めた時の移動距離を答えてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ M $ $ R $ $ r_1 $ $ ... $ $ r_R $ $ A_1 $ $ B_1 $ $ C_1 $ $ : $ $ A_M $ $ B_M $ $ C_M $

输出格式

町を訪れる順番を、道での移動距離が最小となるように決めた時の移動距離を出力せよ。

样例 #1

样例输入 #1
3 3 3
1 2 3
1 2 1
2 3 1
3 1 4
样例输出 #1
2
样例 #2

样例输入 #2
3 3 2
1 3
2 3 2
1 3 6
1 2 2
样例输出 #2
4
样例 #3

样例输入 #3
4 6 3
2 3 4
1 2 4
2 3 3
4 3 1
1 4 1
4 2 2
3 1 6
样例输出 #3
3
提示

制約

$ 2≦N≦200 $

$ 1≦M≦N×(N-1)/2 $

$ 2≦R≦min(8,N) $ ( $ min(8,N) $ は $ 8 $ と $ N $ のうち小さい方)

$ r_i≠r_j (i≠j) $

$ 1≦A_i,B_i≦N , A_i≠B_i $

$ (A_i,B_i)≠(A_j,B_j),(A_i,B_i)≠(B_j,A_j) (i≠j) $

$ 1≦C_i≦100000 $

すべての町の間は道のみで移動することができる。

入力は全て整数である。

Sample Explanation 1

例えば、町 $ 1 $ ,町 $ 2 $ ,町 $ 3 $ の順番で訪れると、移動距離が $ 2 $ となり、最小となります。

Sample Explanation 2

町 $ 1 $ を訪れたあとに町 $ 3 $ を訪れても、町 $ 3 $ を訪れたあとに町 $ 1 $ を訪れても、町 $ 1 $ と町 $ 3 $ の間の最短距離は $ 4 $ であるため、どの順番を選んだとしても答えは $ 4 $ となります。

思路

最短路的题目，由于不确定起点，并且n的范围很小，所以使用Floyd算法可以解决。

题意：给一张无向图，给定一些点，求走过全部给定的点的最小代价。

n<=8，直接全排列然后比大小就行了，floyd n^3的复杂度在n!面前显得微不足道。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const double PI=acos(-1);
const int MAXN=2e5+10;
const ll mod=1e9+7;
const ll INF=1e9;
ll r[8],dis[310][310];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    memset(dis,0x3f3f3f3f,sizeof(dis));
    ll n,m;cin>>n>>m;
    ll R;
    cin>>R;
    for(int i=0;i<R;i++){
        cin>>r[i];
    }
    for(int i=1;i<=m;i++){
        ll x,y,z;
        cin>>x>>y>>z;
        dis[x][y]=dis[y][x]=z;
    }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(dis[i][k]+dis[k][j]<dis[i][j])
                    dis[i][j]=dis[i][k]+dis[k][j];
            }
        }
    }
    sort(r,r+R);
    ll MIN=0;
    ll ans=INF;
    do{
        MIN=0;
        for(int i=0;i<R-1;i++){
            MIN+=dis[r[i]][r[i+1]];
        }
        ans=min(ans,MIN);
    }while(next_permutation(r,r+R));
    cout<<ans;
    return 0;
}