目錄
1.P3853 [TJOI2007] 路標設置
2.P1129 [ZJOI2007] 矩陣游戲
3.P1330 封鎖陽光大學
?4.Trees
5.P1141 01迷宮
1.P3853 [TJOI2007] 路標設置
P3853 [TJOI2007] 路標設置 - 洛谷 | 計算機科學教育新生態 (luogu.com.cn)
先求出每個路標之間的距離，再二分查找每個mid，如果有間距大于mid的，那我們就設立路標，到最后，看新設置的路標數量是否在要求的范圍之內。
#include<iostream>
#include<algorithm>
#include<queue>
#include<math.h>
#include<cstring>
#include<map>
#define ll long long
#define TEST int T;cin>>T;while(T--)
#define lowbit(x) x&(-x)
using namespace std;
const int N = 2000100;
const int M = 1e8 + 7;
int base1 = 131, base2 = 13311;
ll w, n, k;
ll a[N];
bool check(ll x) {ll ans = 0;for (int i = 1; i < n; i++) {if(a[i]>x){ans+=(a[i]-1)/x;}}return ans<=k;
}
void solve() {cin >> w >> n >> k;for (int i = 1; i <= n; i++) cin >> a[i];sort(a + 1, a + 1 + n);for (int i = 1; i <= n - 1; i++) a[i] = a[i + 1] - a[i];ll L = 1, R = w, mid;while (L < R) {mid = L + R >> 1;if (check(mid)) {R = mid ;} else L = mid+1;}cout << R << "\n";
}
int main() {solve();return 0;
}2.P1129 [ZJOI2007] 矩陣游戲
P1129 [ZJOI2007] 矩陣游戲 - 洛谷 | 計算機科學教育新生態 (luogu.com.cn)
其實就是二部圖的最大匹配，在我們給出的矩陣中，我們給(i,j)建邊，當找到的最大匹配大于等于n時，那就說明可以組成一條主對角線的元素都為1。
我們這里用到匈牙利算法。
#include<iostream>
#include<algorithm>
#include<queue>
#include<math.h>
#include<cstring>
#include<map>
#define ll long long
#define TEST int T;cin>>T;while(T--)
#define lowbit(x) x&(-x)
using namespace std;
const int N = 100010;
const int M = 200010;
int base1 = 131, base2 = 13311;
ll n, m, head[N], cnt, colour[N], match[N], v[N];
struct Node {int u, v;
} e[N];
void add(int u, int v) { //鏈式前向星存圖e[++cnt].u = v;e[cnt].v = head[u];head[u] = cnt;
}
void bak()
{for(int i=0;i<=n;i++){e[i].u=e[i].v=v[i]=match[i]=head[i]=0;}cnt=0;
}
bool dfs(int p,int tag)
{if(v[p]==tag) return false;v[p]=tag;for(int i=head[p];i;i=e[i].v){int pos=e[i].u;if(!match[pos]||dfs(match[pos],tag)){match[pos]=p;return true;}}return false;
}
void solve() {cin>>n;for (int i = 1, x; i <= n; i++) {for (int j = 1; j <= n; j++) {cin >> x;if (x) add(i, j );}}ll ans = 0;for (int i = 1; i <= n; i++) {if (dfs(i,i)) ans++;}if (ans >= n) cout << "Yes\n";else cout << "No\n";bak();
}
int main() {TESTsolve();return 0;
}3.P1330 封鎖陽光大學
P1330 封鎖陽光大學 - 洛谷 | 計算機科學教育新生態 (luogu.com.cn)
首先判斷是否構成二分圖，用染色法每次遍歷的時候，答案累加上此時染成兩個集合中元素的最小值。
最后輸出答案。
#include<iostream>
#include<algorithm>
#include<queue>
#include<math.h>
#include<cstring>
#include<map>
#define ll long long
#define TEST int T;cin>>T;while(T--)
#define lowbit(x) x&(-x)
using namespace std;
const int N = 100010;
const int M = 200010;
int base1 = 131, base2 = 13311;
ll n, m, head[N], cnt, colour[N], match[N], v[N], Ans[4];
struct Node {int u, v;
} e[N];
void add(int u, int v) { //鏈式前向星存圖e[++cnt].u = v;e[cnt].v = head[u];head[u] = cnt;
}
bool find1(int x, int tag) {colour[x] = tag;Ans[tag]++;for (int i = head[x]; i; i = e[i].v) {int pos = e[i].u;if (!colour[pos]) {if (!find1(pos, 3 - tag)) return false;} else {if (colour[pos] == tag) return false;}}return true;
}
void solve() {cin >> n >> m;for (int u, v; m; m--) {cin >> u >> v;add(u, v);add(v, u);}ll ans = 0;for (int i = 1; i <= n; i++) {Ans[1] = 0, Ans[2] = 0;if (!colour[i]) {if (!find1(i, 1)) {cout << "Impossible\n";return;}}ans += min(Ans[2], Ans[1]);}cout << ans << "\n";
}
int main() {solve();return 0;
}?4.Trees
2665 -- Trees (poj.org)
先將每個起點和終點排序，安裝具體情況更新L和R，最后答案減去(R-L+1)。
#include<iostream>
#include<algorithm>
#include<queue>
#include<math.h>
#include<cstring>
#include<map>
#define ll long long
#define TEST int T;cin>>T;while(T--)
#define lowbit(x) x&(-x)
using namespace std;
const int N = 5010;
const int M = 200010;
int base1 = 131, base2 = 13311;
ll n, m, head[N], cnt, colour[N], match[N], v[N];
struct Node {ll u, v;
} e[N];
bool cmp(Node a, Node b) {if (a.u == b.u) return a.v < b.v;return a.u < b.u;
}
void solve() {while (cin >> n >> m) {if(n==m&&n==0) break;for (int i = 1; i <= m; i++) {cin >> e[i].u >> e[i].v;if (e[i].u > e[i].v) swap(e[i].u, e[i].v);}sort(e + 1, e + 1 + m, cmp);ll ans = n + 1;ll L = e[1].u, R = e[1].v;for (int i = 2; i <= m; i++) {if (e[i].u <= R) {R = e[i].v;continue;}if (e[i].u > R) {ans -= (R - L + 1);L = e[i].u;R = e[i].v;continue;}}cout << (ans - R + L - 1) << "\n";}
}int main() {solve();return 0;
}5.P1141 01迷宮
P1141 01迷宮 - 洛谷 | 計算機科學教育新生態 (luogu.com.cn)
我們知道，就是尋找按照要求的聯通塊，我們可以用dfs遍歷，這樣詢問時，只需要找到這個位置在哪個聯通塊里面，每個聯通塊的權重就是聯通塊內元素的數量。
#include<iostream>
#include<algorithm>
#include<queue>
#include<math.h>
#include<cstring>
#include<map>
#define ll long long
#define TEST int T;cin>>T;while(T--)
#define lowbit(x) x&(-x)
using namespace std;
const int N = 2000100;
const int M = 1e8 + 7;
int base1 = 131, base2 = 13311;
char mp[1001][1001];
int ans[1001][1001];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
map<ll,ll>f;
int cnt=0;
ll n,m;
void dfs(int x,int y,char tag)
{if(x<1||y<1||x>n||y>n) return;ans[x][y]=cnt;f[cnt]++;for(int i=0;i<4;i++){int tx=x+dx[i];int ty=y+dy[i];if(!ans[tx][ty]&&mp[tx][ty]=='1'-mp[x][y]+'0'){dfs(tx,ty,'1'-mp[x][y]+'0');}}}
void solve() {cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>mp[i][j];}}for(int i=1,x,y;i<=m;i++){cin>>x>>y;if(ans[x][y]) cout<<f[ans[x][y]]<<"\n";else cnt++,dfs(x,y,mp[x][y]),cout<<f[cnt]<<"\n";}
}
int main() {solve();return 0;
}
)
