「团队训练赛」ShanDong Multi-University Training #2
admin
|
|
310
|
团队训练赛

2285 字
|
32 分钟

ShanDong Multi-University Training #2

AEaster Eggs

题目描述：

有a和红色栖息地，b个蓝色栖息地，你需要埋n个彩蛋，可以选择放在红色栖息地，也可以选择放在蓝色栖息地，输出放彩蛋的不同颜色栖息地的最小距离的最大值

思路：

求最小距离的最大值，显然是二分答案

但是怎么check?

两种颜色，可以考虑二分图，但是二分图求什么？

最先思考的应该是给每两个距离大于等于mid的点连边，跑二分图匹配，但是这样真的对吗？显然不对，因为你不能保证所有的不同颜色的之间的距离都大于等于mid

我们考虑一下最大独立集

一个图的最大独立集指的是选出来的尽可能多的点，两两之间没有边连接

所以我们可以考虑建反图，也就是给所有的不同颜色的点之间距离小于mid的点之间连边，再求最大独立集的大小即可

如果最大独立集的大小大于等于n，则满足要求

而 最大独立集 = 点的数量 – 最小点覆盖

最小点覆盖 = 二分图匹配

所以我们check的时候，建个反图，跑二分图匹配，用总的点数a+b – 最大匹配数 来和n比较

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
#define y1 y114514
typedef long long ll;
typedef pair <int,int> pii;
#define eps 1e-9
#define MAX 500 + 50
int n, a, b;
struct ran{
    double x, y;
}ar[MAX], br[MAX];

double dis[MAX][MAX];
bool G[MAX][MAX];
bool vis[MAX];
int link[MAX];

bool dfs(int u){
    for(int v = 1; v <= b; ++v){
        if(!vis[v] && G[u][v]){
            vis[v] = 1;
            if(!link[v] || dfs(link[v])){
                link[v] = u;
                return true;
            }
        }
    }
    return false;
}

bool judge(double mid){
    for(int i = 1; i <= a; ++i){
        for(int j = 1; j <= b; ++j){
            G[i][j] = (dis[i][j] < mid);
        }
    }
    int ans = 0;
    mem(link, 0);
    for(int i = 1; i <= a; ++i){
        mem(vis, 0);
        if(dfs(i))++ans;
    }
    return a + b >= n + ans;
}

double getdis(double x1, double y1, double x2, double y2){
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

void work(){
    cin >> n >> a >> b;
    for(int i = 1; i <= a; ++i)cin >> ar[i].x >> ar[i].y;
    for(int i = 1; i <= b; ++i)cin >> br[i].x >> br[i].y;
    for(int i = 1; i <= a; ++i){
        for(int j = 1; j <= b; ++j){
            dis[i][j] = getdis(ar[i].x, ar[i].y, br[j].x, br[j].y);
        }
    }
    double l = 0, r = 10000.0;
    while(r - l >= eps){
        double mid = (l + r) / 2;
        if(judge(mid))l = mid;
        else r = mid;
    }
    printf("%.9f\n", l);
}


int main(){
    work();
    return 0;
}

B Ilya and a Colorful Walk

题目描述：

n个数，选不同的两个数字a[i]和a[j]，求abs(i - j)的最大值

思路：

考虑一个数组b[i],表示以a[i]为左边的数字时，a[j]下标的最大值

对于a[i]来说，如果a[i] != a[n],则b[i] = n

否则b[i]等于从n开始往前找第一个不等于a[n]的点的下标

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x;
int tr[MAX];

void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i)cin >> tr[i];
    int ans = 0;
    for(int i = n - 1; i >= 1; --i){
        if(tr[i] != tr[n]){
            x = i;break;
        }
    }
    for(int i = 1; i <= n; ++i){
        if(tr[i] != tr[n])ans = max(ans, n - i);
        else ans = max(ans, abs(x - i));
    }
    cout << ans << endl;
}


int main(){
    io;
    work();
    return 0;
}

D Transmitters

题目描述：

给一个半圆，和若干个点，半圆可以绕着圆心旋转，问最多能包含多少个点

思路：

首先，如果有点在直径上肯定是最优的，这样能腾出更多的地方给别的点，所以我们可以枚举每个点在直径的情况，现在只需要利用叉积求剩下的点在直线的两边，且在半圆内的点的数量a,b，和在直线上的数量c，计算最大值max(a + c, b + c)，求一个最大的即可

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x;
double r;

const double DINF = 1e18, eps = 1e-8;
struct Point{
    double x, y;
    Point(double x = 0, double y = 0):x(x), y(y){ }//构造函数
};
Point st;
Point tr[MAX];
typedef Point Vector;
Vector operator + (Vector A, Vector B){return Vector(A.x + B.x, A.y + B.y);}
Vector operator - (Point A, Point B){return Vector(A.x - B.x, A.y - B.y);}
Vector operator * (Vector A, double p){return Vector(A.x * p, A.y * p);}
Vector operator / (Vector A, double p){return Vector(A.x / p, A.y / p);}
bool operator < (const Point& a, const Point& b) {return a.x < b.x || (a.x == b.x && a.y < b. y);}
double Polar_angle(Vector A){return atan2(A.y, A.x);}

int sgn(double x){
    if(fabs(x) < eps)
        return 0;
    if(x < 0)
        return -1;
    return 1;
}
bool operator == (const Point& a, const Point& b){return !sgn(a.x - b.x) && !sgn(a.y - b.y);}

double Cross(Vector A, Vector B){return A.x *  B.y - B.x * A.y;}

int relation(Point A, Point B, Point C)
{
    // 1 left -1 right 0 in
    int c = sgn(Cross((B - A), (C - A)));
    if(c < 0) return 1;
    else if(c > 0) return -1;
    return 0;
}

bool judge(Point a, Point b){
    return r < sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

int ans;

void cal(int id){
    int a = 0, b = 0, c = 0;
    for(int i = 1; i <= n; ++i){
        if(!judge(st, tr[i])){
            int d = relation(st, tr[id], tr[i]);
            if(d == 1)++a;
            else if(d == -1)++b;
            else ++c;
        }
    }
    ans = max(ans, max(a + c, b + c));
}


void work(){
    while(cin >> st.x >> st.y >> r >> n){
        for(int i = 1; i <= n; ++i){
            cin >> tr[i].x >> tr[i].y;
        }
        ans = 0;
        for(int i = 1; i <= n; ++i){
            cal(i);
        }
        cout << ans << endl;
    }
}


int main(){
    io;
    work();
    return 0;
}

 

E. Lowbit

题目描述：

两种操作

  • 给区间的每个数x加上他们的lowbit(x)
  • 求区间和

思路：

经典势能线段树

一个非2的幂次方的数字加lowbit几次后一定会变成2的幂次方，此时再加lowbit，就相当于乘2

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ls p<<1
#define rs p<<1|1
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 500000 + 50
int n, m;
int op, l, r;
ll tr[MAX];
ll la[MAX];
int ar[MAX];
bool vis[MAX];

bool judge(ll x){
    return x == lowbit(x);
}

void pushup(int p){
    (tr[p] = tr[ls] + tr[rs]) %= mod;
    vis[p] = vis[ls] & vis[rs];
}

void cal_lazy(int p, ll c){
    (tr[p] *= c) %= mod;
    (la[p] *= c) %= mod;
}

void pushdown(int p){
    if(la[p] != 1){
        cal_lazy(ls, la[p]);
        cal_lazy(rs, la[p]);
        la[p] = 1;
    }
}

void built(int p, int l, int r){
//    tr[p] = 0;
    la[p] = 1;
    vis[p] = 0;
    if(l == r){
        tr[p] = ar[l];
        if(judge(tr[p]))vis[p] = 1;
        return;
    }
    int mid = (l + r) / 2;
    built(ls, l, mid);
    built(rs, mid + 1, r);
    pushup(p);
}

void update(int p, int l, int r, int s, int t){
    if(l >= s && r <= t && vis[p]){
        cal_lazy(p, 2);
        return;
    }
    if(l == r){
        tr[p] += lowbit(tr[p]);
//        (tr[p] = (ar[l] += lowbit(ar[l]))) %= mod;
        if(judge(tr[p]))vis[p] = 1;
        return;
    }
    pushdown(p);
    int mid = (l + r) / 2;
    if(mid >= s)update(ls, l, mid, s, t);
    if(mid < t)update(rs, mid + 1, r, s, t);
    pushup(p);
}

ll getans(int p, int l, int r, int s, int t){
    if(l >= s && r <= t)return tr[p];
    pushdown(p);
    int mid = (l + r) / 2;
    ll ans = 0;
    if(mid >= s)(ans += getans(ls, l, mid, s, t)) %= mod;
    if(mid < t)(ans += getans(rs, mid + 1, r, s, t)) %= mod;
    return ans;
}

void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i)cin >> ar[i];
    built(1, 1, n);
    cin >> m;
    while(m--){
        cin >> op >> l >> r;
        if(op == 1)update(1, 1, n, l, r);
        else cout << getans(1, 1, n, l, r) << endl;
    }
}


int main(){
    io;
    int tt;cin>>tt;
    for(int _t = 1; _t <= tt; ++_t){
        work();
    }
    return 0;
}

F Lemonade Trade

题目描述：

你有一升粉色饮料，想换取蓝色饮料

有n个商人，每个商人可以将1升b饮料换成p升a饮料，p是汇率，只能从1到n顺次访问商人，到每个商人的地方可以选择换或不换，换的量也可以任意，不可以回头

问最多能获得多少蓝色的饮料，如果能换的蓝色饮料大于10升，则输出10即可

思路：

一眼DP

设dp[i]表示能换出i的饮料的体积的最大值

则对于一个商人，假设1升a可以换p升b，dp[b] = max(dp[b], dp[a] * p)

但是如果都是大于1的汇率，很快就会乘爆，所以我们可以考虑用用log来将乘法降级为加法

dp[b] = max(dp[b], dp[a] + log10(p))

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define MAX 300050
int n;
double p;
string s, t;
map<string, double>dp;

void work()
{
    cin >> n;
    dp["pink"] = 0.0;
    for(int i = 1; i <= n; ++i)
    {
        cin >> s >> t >> p;
        if(dp.count(t))
        {
            if(!dp.count(s))dp[s] = dp[t] + log10(p);
            else dp[s] = max(dp[s], dp[t] + log10(p));
        }
    }
    if(dp["blue"] == 0)printf("0.00000000\n");
    else if(dp["blue"] - 1 >= 1e-8)printf("10.00000000\n");
    else printf("%.8lf\n", pow(10.0, dp["blue"]));

}

int main()
{
    work();
    return 0;
}

I Love Rescue

题目描述：

给两个串s,t

你可以选择一些双向转换规则，使得s能变成t

问选哪些

思路：

简单并查集，s[i] 如果不想等t[i]，就看看合并过没，如果没合并，则合并，否则不需要。

最后输出的时候判断26个字母i的fa[i]是否相等，不想等的话输出就行，相等的话就需要输出

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n;
string s, t;
int fa[MAX];
int getfa(int x){
    return fa[x] == x ? x : fa[x] = getfa(fa[x]);
}
void emerge(int x, int y){
    fa[getfa(x)] = getfa(y);
}

void work(){
    cin >> n >> s >> t;
    for(int i = 1; i <= 26; ++i)fa[i] = i;
    int ans = 0;
    for(int i = 0; i < s.size(); ++i){
        int a = s[i] - 'a' + 1;
        int b = t[i] - 'a' + 1;
        if(getfa(a) != getfa(b)){
            ++ans;
            emerge(a, b);
        }
    }
    cout << ans << endl;
    for(int i = 1; i <= 26; ++i){
        if(getfa(i) != i)cout << (char)('a' + i - 1) << ' ' << (char)('a' - 1 + getfa(i)) << endl;
    }
}


int main(){
    io;
    work();
    return 0;
}

J Flip,Flip, and Flip……

题目描述：

给你n * m的矩阵，最开始的值都是0，以每个点为中心点的3 * 3的矩阵都取反一次，顺序任意，问最终有几个1

思路：

当min(n, m) >= 2时，只有矩阵的上下左右边界的反转次数是偶数，答案是(n - 2) * (m - 2)

其他情况特判就行

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main()
{
    ll n, m;
    cin >>n >> m;
    if(n >= 2 && m >= 2)cout <<(n - 2) * (m - 2) <<endl;
    else if(n == 1 && m == 1)cout <<1ll <<endl;
    else if(n == 1 && m != 1)cout << m - 2 <<endl;
    else cout << n - 2 <<endl;
    return 0;
}

K Dividing Subsequence

题目描述：

两个序列ar,br,分别选择k个数，满足br[i] % ar[i] == 0, 1<= i <= k，问k最大是多少

思路：

类似于最长公共子序列，不过最长公共子序列满足的是ar[i] = br[i]，而这里满足的是br[i] % ar[i] == 0

最长公共子序列的做法是将br的每个数字映射到ar中相同的数字的位置的下标，然后求一次最长上升子序列

这个题也差不多，一个br[i]能对应很多个下标，这个我们可以处理出来，时间大概是O(nlogn)

我们可以处理成计作一个二维的pair,第一维是br[i]本来的下标i，第二维是所有满足br[i] % ar[j] == 0的下标j，我们按照第一维度从小到大排序，第二维度从大到小排序

第一维度从小到大排序的目的是使得这个序列顺序是正常的

第二维度从大到小排序的目的是防止求LIS的时候同一个数选择多次

所以我们只需要对第二维度的数求一遍最长上升子序列就行

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x;
int tr[MAX];
int ar[MAX];
int br[MAX];
int id[MAX];
vector<pii>v;
vector<int>dp;
void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i)cin >> ar[i];
    for(int i = 1; i <= n; ++i)cin >> br[i];
    for(int i = 1; i <= n; ++i)id
] = i;
    for(int i = 1; i <= n; ++i){
        for(int j = ar[i]; j <= n; j += ar[i])v.push_back(m_p(id[j], -i));
    }
    sort(v.begin(), v.end());
//    for(auto [x, y] : v)cout << x << ' ' << -y << endl;
    dp.push_back(-v[0].second);
    for(int i = 1; i < v.size(); ++i){
        if(dp.back() < -v[i].second){
            dp.push_back(-v[i].second);
        }
        else{
            dp[lower_bound(dp.begin(), dp.end(), -v[i].second) - dp.begin()] = -v[i].second;
        }
    }
    cout << dp.size() << endl;
}


int main(){
    io;
    work();
    return 0;
}

总结

这场比赛发挥的很不好

比赛一开始，yj去开了一个G题，做到最后也没写出来，导致只有我和djk两个人开题做题

最开始跟棒写了个B，交不上去，等了20分钟才爆了个wa回来，发现是没break，又交了一发，一直等到J过了以后几分钟后才返回B的AC，

这个时候没人开题，我一看出题少罚时高有点急，就自己去开了一个L题，发现有点简单，写了两个式子就拿了个一血，然后就开始写F的dp，wa了一发以后就发现会乘爆，不知道怎么改，然后就被抓去开会，开完的时候想起来可以用log去优化，开完会就偷偷溜回去写了，调了一会就过了，然后就被抓去全校核酸，打了大概三个半小时

结束以后一看E是原题，势能线段树的经典题目，血亏

I题也是个sb题，一眼就会，只可惜当时没读题

还有两个题都差一点就想出正解，如果yj不纠结G题，而是帮我俩想别的题，说不定能出更多的题…

博客内容均系原创，未经允许严禁转载！
团队赛
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																					

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
「团队赛」2022 Jiangsu Collegiate Programming Contest「A模拟」「B 优先队列优化dp」「I 思维」「J 记忆化+暴力打表」「K 二进制构造」「L 思维」

							
							

							
「团队训练赛」The 14th Jilin Provincial Collegiate Programming Contest「ABCEFGJLM」

							
							

							
「团队训练赛」The 2021 Sichuan Provincial Collegiate Programming Contest 题解

							
							

							
「团队训练赛」ShanDong Multi-University Training #3

							
							

							
2016 ACM-ICPC NCPC 题解