文章目录
- C - Connections
- D - Designing the Toy
- A - Archery Tournament
- L. Laminar Family
- 总结
C - Connections
题目链接
思维
题意：给你一张能到达任意点的图， m > 2 ? n , m < 100000 m>2*n, m<100000 m>2?n,m<100000，删掉 m ? 2 ? n m-2*n m?2?n条路使这张图仍然能到达任意点
本来就考虑这张图找一个环，后来发现会有很多环。题目留下 2 ? n 2*n 2?n条就是找 1 1 1到其他点和其他点到 1 1 1的路，总不可能真的找其他点到一的路，所以就是跑一遍正向的图和反向的图从 1 1 1开始
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+6;
vector<pair<int, int> > g[N], fan[N];
pair<int, int> a[N];
bool vis[N], vis1[N];
void dfs(int u) {
vis[u]=1;for(auto v:g[u]) {
int x=v.first;if(!vis[x]) {
vis1[v.second]=1;dfs(x);}}
}
void dfs1(int u) {
vis[u]=1;for(auto v:fan[u]) {
int x=v.first;if(!vis[x]) {
vis1[v.second]=1;dfs1(x);}}
}
signed main() {
int t; cin>>t;while(t--) {
int n, m; cin>>n>>m;for(int i=1; i<=n; i++) g[i].clear(), fan[i].clear();for(int i=1; i<=m; i++) {
int x , y; cin>>x>>y;g[x].push_back(make_pair(y, i));fan[y].push_back(make_pair(x, i)); //建反向边a[i]=make_pair(x, y);vis1[i]=0;}for(int i=1; i<=n; i++) vis[i]=0;dfs(1);for(int i=1; i<=n; i++) vis[i]=0;dfs1(1);int cnt=m-2*n;for(int i=1; i<=m; i++)if(!vis1[i]) {
cnt--;cout<<a[i].first<<" "<<a[i].second<<endl;if(cnt==0) break;}}return 0;
}
D - Designing the Toy
题目链接
思维
题意：给你三视图的面积 a b c abc abc
让你用 1 ? 1 ? 1 1 * 1 * 1 1?1?1的立方体构造满足 a b c abc abc
补
先在000放一个 abc都-1
如果 a < b ? c a<b*c a<b?c 就放001 002 003…
直到 a > b ? c a>b*c a>b?c就可以在一个面上放了
再分类讨论 a a a和 b c b c bc的情况
图是a>=b+c的情况
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N=1e5+5;
int a[5];
struct node {
int x, y, z;
};
vector<node> ans;
int main() {
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);int a, b, c;cin>>a>>b>>c;if(a>b*c||b>c*a||c>a*b) {
cout<<-1<<endl;return 0;}ans.push_back({
0,0,0});a--,b--,c--;int cnt=0;while(a<b*c) {
b--, c--;ans.push_back({
0,0,++cnt});} if(a>=b+c) {
// 可以把两边都铺满, a是足够的for(int i=1; i<=b; i++) ans.push_back({
i,0,0}), a--;for(int i=1; i<=c; i++) ans.push_back({
0,i,0}), a--;if(a) {
// 有可能a > b + c, 铺满两边再在中间乱放for(int i=1; i<=b; i++) {
for(int j=1; j<=c; j++) {
ans.push_back({
i,j,0});a--;if(!a) break;}if(!a) break;}} // a == b * c and a < b + c, 只可能有两种情况}else if(a==b*c) {
// 情况1: 有一个是1了, 往上移动1个if(c==1)for(int i=1; i<=b; i++) ans.push_back({
i,1,0});else if(b==1)for(int i=1; i<=c; i++) ans.push_back({
1,i,0});}else{
//情况2: 有一个是0if(!b) {
for(int i=1; i<=a; i++) ans.push_back({
0,i,0}), c--;if(c) {
for(int i=1; i<=a; i++) {
for(int j=1; j<=cnt; j++) {
// cnt是z轴的高度ans.push_back({
0,i, j});c--;if(!c) break;}if(!c) break;}}}else if(!c) {
//2for(int i=1; i<=a; i++) ans.push_back({
i,0,0}), b--;if(b) {
for(int i=1; i<=a; i++) {
for(int j=1; j<=cnt; j++) {
ans.push_back({
i,0, j});b--;if(!b) break;}if(!b) break;}}}}cout<<ans.size()<<endl;for(auto v:ans) {
cout<<v.x<<" "<<v.y<<" "<<v.z<<endl;}return 0;
}
A - Archery Tournament
题目链接
乱搞或线段树+set
题意：给出n个操作，
操作1表示建立一个位于(x,y)且半径为y的靶子。
操作2表示往（x,y）处开一枪。
要求在每次开枪的时候，给出枪是否命中了靶子，若命中了则输出靶子的编号，并且删除这个靶子，若没有命中则输出-1
补
用set存左右边界然后二分直接找两边的好像不太行
然后换思路二分找（当前x-最大半径）之后的圆 check
但是找到最后会 t 所以只要找到的圆心的 x x x 小于（当前x+最大半径）就可以了
线段树做法
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005;
struct node {
int x, y, id;bool operator<(const node &rhs)const{
return x<rhs.x;}
};
set<node> se;
signed main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);int n; cin>>n;int mr=0;for(int i=1; i<=n; i++) {
int x, y, op; cin>>op>>x>>y;if(op==1) {
se.insert({
x, y, i});mr=max(mr, y);}else {
set<node>::iterator it = se.lower_bound({
x-mr, y, 0}); //直接找大于等于 x 会漏bool flag=0;while(it!=se.end()) {
node pp=(*it);if(pp.x>x+mr) break; //没有了就breakif((pp.x-x)*(pp.x-x)+(pp.y-y)*(pp.y-y)<pp.y*pp.y) {
cout<<pp.id<<endl;se.erase(it);flag=1;break;}it++;}if(!flag) cout<<-1<<endl;}}return 0;
}
L. Laminar Family
题目链接
树链剖分+LCA+线段树
题意：给出一棵树和一组操作，操作的格式是给出 u v uv uv两个节点，并将该节点所确定的路径上的节点全部加入到一个新的集合里面去。
如果所有的集合中任意两个均满足，要么互相包含，要么不相交，则输出Yes，否则输出No
未补
贴上佬的代码
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
template <typename T>
void read(T & x){
x = 0;T f = 1;char ch = getchar();while(!isdigit(ch)){
if(ch == '-') f = -1;ch = getchar();}while (isdigit(ch)){
x = x * 10 + (ch ^ 48);ch = getchar();}x *= f;}using namespace std;
const int N = 100010, M = N << 1;int n, m, idx, ne[M], e[M], h[N];
int sz[N], dep[N], fa[N], son[N], f[N][20], id[N], tot, top[N];
struct node{
int l, r, col, lz;
}tr[N << 2];
struct Q{
int l, r, dep, id;bool operator < (const Q& rhs) const{
return dep > rhs.dep;}
}; vector<Q> Qu;
void GG(){
cout << "No"; exit(0); }
void add(int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;}
void pushup(int u){
tr[u].col = (tr[u << 1].col == tr[u << 1 | 1].col ? tr[u << 1].col : -1);}
void pushdown(int u){
node& rt = tr[u], &le = tr[u << 1], &ri = tr[u << 1 | 1];if(!rt.lz) return ;le.lz = ri.lz = le.col = ri.col = rt.lz;rt.lz = 0;
}
void build(int u, int l, int r){
tr[u] = {
l, r, 0, 0};if(l == r) return ;int mid = l + r >> 1;build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}
int modify(int u, int l, int r, int new_col){
if(tr[u].l >= l and tr[u].r <= r){
if(tr[u].col == -1) GG();int res = tr[u].col;tr[u].col = new_col, tr[u].lz = new_col;return res;}pushdown(u);int mid = tr[u].l + tr[u].r >> 1, ri = -2, le = -2;if(l <= mid) le = modify(u << 1, l, r, new_col);if(r > mid) ri = modify(u << 1 | 1, l, r, new_col);if(ri != -2 and le != -2 and ri != le) GG();pushup(u);return max(le, ri);
}
void dfs1(int u, int father){
sz[u] = 1, dep[u] = dep[father] + 1, fa[u] = father;for(int i = h[u]; ~i; i = ne[i]){
int j = e[i];if(j == father) continue ;f[j][0] = u;for(int k = 1; k <= 19; ++ k) f[j][k] = f[f[j][k - 1]][k - 1];dfs1(j, u);sz[u] += sz[j];if(sz[son[u]] < sz[j]) son[u] = j;}
}
void dfs2(int u, int t){
id[u] = ++ tot, top[u] = t;if(!son[u]) return ;dfs2(son[u], t);for(int i = h[u]; ~i; i = ne[i]){
int j = e[i];if(j == fa[u] or j == son[u]) continue ;dfs2(j, j);}
}
int lca(int a, int b){
if(dep[a] < dep[b]) swap(a, b);for(int i = 19; i >= 0; -- i) if(dep[f[a][i]] >= dep[b]) a = f[a][i];if(a == b) return a;for(int i = 19; i >= 0; -- i) if(f[a][i] != f[b][i]) a = f[a][i], b = f[b][i];return f[a][0];
}
void query_path(int u, int v, int new_col){
int res = -2;while(top[u] != top[v]){
if(dep[top[u]] < dep[top[v]]) swap(u, v);int now = modify(1, id[top[u]], id[u], new_col);if(res == -2) res = now;else if(res != now) GG();u = fa[top[u]];}if(dep[u] < dep[v]) swap(u, v);int now = modify(1, id[v], id[u], new_col);if(res == -2) res = now;else if(res != now) GG();
}
signed main(){
read(n), read(m);memset(h, -1, sizeof h);for(int i = 1, a, b; i <= n - 1; ++ i){
read(a), read(b);add(a, b), add(b, a);}memset(dep, 0x3f, sizeof dep); dep[0] = 0;dfs1(1, 0);dfs2(1, 1);build(1, 1, n);for(int i = 1; i <= m; ++ i){
int l, r;read(l), read(r);int LCA = lca(l, r);Qu.push_back({
l, r, abs(dep[l] + dep[r] - 2 * dep[LCA]), i});}sort(all(Qu));for(auto u : Qu) query_path(u.l, u.r, u.id);cout << "Yes" << endl;return 0;
}