排座位

作者 陳越 單位 浙江大學 代碼長度限制 16KB 時間限制 200 ms 記憶體限制 64 MB

題意

• 輸入n,k,m，n表示一共有n個人要進行排座位，m條關系條數（A B S i S_i Si?）表示A和B之間的關系為 S i S_i Si?，然后進行k次查詢，問兩人是否能連著坐在一起

• 關系為1表示是朋友，-1表示是死對頭

• 對每個查詢輸出一行結果：

  • 如果兩位賓客之間是朋友，且沒有敵對關系，則輸出No problem；
  • 如果他們之間并不是朋友，但也不敵對，則輸出OK；
  • 如果他們之間有敵對，然而也有共同的朋友，則輸出OK but…；
  • 如果他們之間只有敵對關系，則輸出No way，

題解

通過二維陣列存盤兩人之間的關系，由于兩人之間的關系是唯一的，所以可以看做是 雙向邊

純列舉做法不管怎么改都過不去,而最好的情況也會有全聯通的測驗點無法通過，因此判斷是后能滿足條件

因此，上網查詢了一下并查集做法

未得分點：最大N，全連通環，全查詢

acwing并查集 模板題

find(x) 是找會祖宗節點， p[x] 陣列存放的是父節點

代碼

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int MAXN = 111;
int p[MAXN];
int find(int x) {
    if (p[x] == x) return p[x];
    return p[x] = find(p[x]);
}

//把能夠成為好友的全部合并到一個根上
void merge(int x, int y){
    int t1 = find(x);
    int t2 = find(y);
    if (t1 != t2){
        p[t1] = t2;
    }
}

int gx[MAXN][MAXN];

int main(){
    int n, m, k; scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= n; i++)  p[i] = i;
    for(int fi = 1; fi <= m; ++fi) {
        int a, b, c; scanf("%d%d%d", &a, &b, &c);
        gx[a][b] = c; gx[b][a] = c;
        if (c == 1) merge(a, b);
    }
    for(int qu = 1; qu <= k; ++qu){
        int qa, qb; scanf("%d%d", &qa, &qb);
        if (gx[qa][qb] == 1) puts("No problem");
        else if (gx[qa][qb] == -1){ if (find(qa) == find(qb))puts("OK but..."); else puts("No way");}
        else {if (find(qa) == find(qb)) puts("No problem"); else puts("OK");}
    }
}

7-12 分而治之

題意

我們希望首先攻下敵方的部分城市，使其剩余的城市變成孤立無援，然后再分頭各個擊破，為此參謀部提供了若干打擊方案，本題就請你撰寫程式，判斷每個方案的可行性，

題解

• 建圖，資料大小和多邊的存在，因此更適合vector的動態二維陣列去建立鄰接表，像最短路那樣建

• 處理，通過vis去進行標記，vis[x] = 1說明這個城市已經被攻下了

• 訪問，通過兩層for回圈去進行遍歷，外層城市總數，內層該城市所連接的v[i].size()座城市

• 當 v i s [ i ] = = 0 且 v i s [ v [ i ] [ j ] ] = = 0 vis[i] == 0 且 vis[v[i][j]] == 0 vis[i]==0且vis[v[i][j]]==0的時候就說明存在城市不是孤立無援的，因此直接標記為策略失敗

代碼

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 1111;
const int N = 111;
int vis[maxn];
vector<int> v[maxn]; // 鏈接表
void init1(){
    memset(vis, 0, sizeof vis);
}
int main(){
    int n, m; cin >> n >> m;
    for(int si = 1; si <= m; si++){
        int a, b; cin >> a >> b;
        //雙向邊
        v[a].push_back(b);
        v[b].push_back(a);
    }
    int k; cin >> k;

    // k種方案,使其剩余的城市變成孤立無援
    
    for(int sk = 1; sk <= k; ++sk){
        
        bool flag = true; //用于判斷是否能夠攻擊成功
        init1(); 
        
        int np; cin >> np;
        for(int sp = 1; sp <= np; ++sp){
            int x; cin >> x; vis[x] = 1; //x城市已經被進攻
        }

       for(int i = 0; i < n; i++){
            for(int j = 0; j < v[i].size(); j++){
                if (vis[i] == 0 && vis[v[i][j]] == 0){
                    //確保都沒進攻過
                    flag = false;
                }
            }
       }
       (flag) ? puts("YES") : puts("NO");
    }
}

垃圾桶分布

題意

從m個垃圾站里面選取1個站點，讓該站點離居民區的最近的人最遠，并且沒有超出服務范圍ds之內，

如果有很多個最遠的垃圾站，輸出距離所有居民區距離平均值最小的那個，如果平均值還是一樣，就輸出按照順序排列垃圾站編號最小的那個

型別

最短路+字符處理

題解

\\沒寫完，別看別看別看
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1E5 + 50;
int d[MAXN];
bool vis[MAXN];//優化,判斷是否松弛過
vector<pair<int, int >> E[MAXN];
inline void init(){
	for(int i = 0; i < MAXN; i++) d[i] = INF;
	for(int i = 0; i < MAXN; i++) E[i].clear();
	for(int i = 0; i < MAXN; i++) vis[i] = false;
}
//迪杰斯特拉
void dij(){
	   int n, m, s; scanf("%d%d%d", &n, &m, &s);
		priority_queue <PII, vector< PII >, greater<PII >> p;
        init();
		REP(i, m){
			int x, y, z; RD(x, y, z);
			E[x].push_back(MP(y, z));
		}
		//Dij
		p.push(PII( 0, s)), d[s] = 0;
		while(!p.empty()){
			pair<int, int> now = p.top(); p.pop();
            if (now.first != d[now.second])continue;
			for(PII u: E[now.second]){
				if (d[u.first] > d[now.second] + u.second){
					d[u.first] = d[now.second] + u.second; 
					p.push(make_pair(d[u.first], u.first));
				}
				
			}
		}
		FOR_1(i, 0, n - 1){
			if (d[i] == INF) cout << "INF" << '\n';
			else cout << d[i] << '\n';
		}
}
int main(){
	int n, m, k, ds; cin >> n >> m >> k >> ds;
	

	return 0;
}