首页 > 其他分享 >2022 China Collegiate Programming Contest (CCPC) Guilin Site

2022 China Collegiate Programming Contest (CCPC) Guilin Site

时间：2024-04-09 17:45:20浏览次数：38  
标签：std Contest int LL Guilin kN long Site maxl

目录

写在前面

比赛地址：https://codeforces.com/gym/104008。

以下按个人向难度排序。

三月初 vp，vp 完就去打华为软挑了，拖到现在才补题解呃呃。

唉华为软挑打得也是一拖，感觉没有活着的价值。

A

签到。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1010;
//=============================================================
int pre[kN], next[kN];
std::string s;
//=============================================================
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  int n; std::cin >> n;
  std::cin >> s;
  for (int i = 0; i < n; ++ i) {
    if (s[i] == 'L') pre[i] = i;
    else if (i != 0) pre[i] = pre[i - 1];
    else pre[i] = -100;
  }
  for (int i = n - 1; i >= 0; -- i) {
    if (s[i] == 'L') next[i] = i;
    else if (i != n - 1) next[i] = next[i + 1];
    else next[i] = n + 100;
  }

  for (int i = 0; i < n; ++ i) {
    if (s[i] == 'L') std::cout << 'L';
    else if (pre[i] < i - 1 && next[i] > i + 1) std::cout << 'C';
    else std::cout << '.';
  }
  return 0;
}

M

树状数组。

没看题，咕。

Code by dztle：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=600005;
#define lowbit(x) x&(-x)
int n,m;
int a[N],t[N],q[N*3];
char s[N];
void add(int x,int k){
	while(x<=n){
		t[x]+=k;
		x+=lowbit(x);
	}
}
int query(int x){
	int ans=0;
	while(x){
		ans+=t[x];
		x-=lowbit(x);
	}
	return ans;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		cin>>a[i];
	}
	int Sum=0;
	for(int i=n;i>=1;--i){
		Sum+=query(a[i]);
		add(a[i],1);
	}
	scanf("%s",s);
	int cnt=0,fl=0,l=N,r=l+n-1;
	for(int i=1;i<=n;++i){
		q[l+i-1]=a[i];
	}
	cout<<Sum<<endl;
	for(int i=0;i<m;++i){
		if(s[i]=='S'){
			if(fl==1){
				Sum=Sum-(q[r]-1)+(n-q[r]);
				q[l-1]=q[r]; --r,--l;
			}else{
				Sum=Sum-(q[l]-1)+(n-q[l]);
				q[r+1]=q[l]; ++l,++r;
			}
		}else{
			Sum=(n*(n-1)/2)-Sum;
			fl=!fl;
		}
		cout<<(Sum%10+10)%10;
//		cout<<Sum<<endl;
	}
	return 0;
}

C

手玩结论题。

发现经过一次操作二之后，操作一二的影响变为相同，于是考虑枚举第几次操作时进行操作二即可。

更进一步地，将最终的贡献式展开发现最终答案只有两种情况：要么一直进行操作一，要么第一步就进行操作二。取最大值即可。

Code by dztle：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;const int N=1e5+5,mod=1e9+7;
int a[N],b[N],sum;
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		cin>>a[i];
		sum+=a[i];
		b[i]=a[i]+b[i-1];
	}
	int pre=0;
	for(int i=1;i<=n;++i) pre+=b[i];
	int A=pre,B=(2*n+1)*sum;
	for(int i=1;i<=m;++i){
		A=2*A%mod+n*sum%mod;
		A%=mod;
		B=(2*n+1)*sum%mod;
		n=n*2%mod;
		sum=sum*2%mod;
	}
	cout<<max(A,B);
	return 0;
}

E

数学。

赛时猜了个假结论在线段中点处找 50 个点检查 WA 成构式耻辱下班、、、

记已知的两个点为 \(A, B\)，未知的点为 \(C\)，则最小化 \(S_{\triangle ABC}\) 等价于最小化 \(\frac{1}{2} \left|\overrightarrow{AB} \times \overrightarrow{AC}\right|\)。记 \(\overrightarrow{AB} = (a, b), \overrightarrow{AC} = (c, d)\)，代入可得只需最小化 \(\frac{1}{2} \left| ad - bc \right|\)，其中 \(a, b\) 为已知参数。

发现是一个经典的二元一次不定方程形式，由裴蜀定理 \(|ad - bc|\) 最小值为 \(\gcd(a, b)\)，扩展欧几里得解出一组任意解 \((c, d)\) 后即可得到 \(C\) 的坐标。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
LL x1, y1, x2, y2;
//=============================================================
LL exgcd(LL a_, LL b_, LL &x_, LL &y_) {
  if (!b_) {
    x_ = 1, y_ = 0;
    return a_;
  }
  LL d_ = exgcd(b_, a_ % b_, y_, x_);
  y_ -= a_ / b_ * x_;
  return d_;
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  int T; std::cin >> T;
  while (T --) {
    std::cin >> x1 >> y1 >> x2 >> y2;
    LL a = y2 - y1, b = x1 - x2, f1 = 1, f2 = 1;
    if (a < 0) f1 = -1, a = -a;
    if (b < 0) f2 = -1, b = -b;

    LL x3, y3, d = exgcd(a, b, x3, y3);
    x3 = x3 * f1, y3 = y3 * f2;

    std::cout << (x2 - x3) << " " << (y2 - y3) << "\n";
  }
  return 0;
}

L

手玩诈骗题。

数据范围这么小是因为 checker 时间复杂度是指数级的呃呃，还以为是不可做的神题太诈骗了

样例三对最终做法是有启发性的。

一个很显然的想法是所有人应当尽量选大的，且若一个数字被选择了两次则之后再选均无贡献。则一种构造方案是：

  • 玩家 1,2：\(100\%\) 概率选择 \(m\)。
  • 玩家 3,4：\(100\%\) 概率选择 \(m-1\)。
  • ……
  • 玩家 \(n\)：\(100\%\) 概率选择 \(m-\left\lfloor\frac{n - 1}{2}\right\rfloor\)。

发现此时对于任意玩家，无论调整到更大的数还是更小的数均无法成为胜者——要么大家都挂掉，要么使其他人成为了胜者，达到了纳什均衡状态。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 20;
//=============================================================
//=============================================================
double ans[kN][kN];
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  int n, m; std::cin >> n >> m;
  int temp = n;
  for (int i = m;  i; -- i) {
    ans[temp --][i] = 1;
    if (!temp) break;
    ans[temp --][i] = 1;
    if (!temp) break;
  }
  while (temp) ans[temp --][m] = 1;

  for (int i = 1; i <= n; ++ i) {
    for (int j = 1; j <= m; ++ j) {
      std::cout << std::fixed << std::setprecision(10) << ans[i][j] << " ";
    }
    std::cout << "\n";
  }
  return 0;
}

G

换根 DP。

第一次见这种换根 DP 的写法，牛逼。

大力手玩下，发现最优的情况下，两条路径至多有一个交点。则最终有贡献的节点构成的形态一定为下列两种情况之一：

  • 以某个节点 \(u\) 为一端的四条链（不包含节点 \(u\)，且长度可为 0）。
  • 两条不相交的路径。

若不为上述两种形态，则可以通过添加某些节点调整成上述两种形态，且获得更多的贡献。

第一种情况非常简单，换根 DP 维护以每个节点为端点的所有链，并按长度排序，枚举所有节点取其中长度前 4 大的即可。

第二种情况实际上可看做断开树中的一条边，在得到的两根树分别求带权直径。这是一般的换根 DP 实现起来比较麻烦的。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
#define mp std::make_pair
const int kN = 2e5 + 10;
//=============================================================
int n, a[kN];
int edgenum, head[kN], v[kN << 1], ne[kN << 1];
int ans;
std::vector <std::pair <int, int> > maxl[kN];
std::map <int, int> f[kN];
//=============================================================
void Add(int u_, int v_) {
  v[++ edgenum] = v_;
  ne[edgenum] = head[u_];
  head[u_] = edgenum;
}
void Dfs1(int u_, int fa_) {
  for (int i = head[u_]; i; i = ne[i]) {
    int v_ = v[i];
    if (v_ == fa_) continue;
    Dfs1(v_, u_);
    maxl[u_].push_back(mp(a[v_], v_));
    if (!maxl[v_].empty()) maxl[u_].back().first += maxl[v_][0].first;
  }
  std::sort(maxl[u_].begin(), maxl[u_].end(), std::greater <std::pair <LL, int> >());
}
void Dfs2(int u_, int fa_, int dis_) {
  if (fa_) {
    maxl[u_].push_back(mp(dis_, fa_));
    std::sort(maxl[u_].begin(), maxl[u_].end(), std::greater <std::pair <LL, int> >());
  }
  while (maxl[u_].size() < 4) maxl[u_].push_back(mp(0, 0)); 

  for (int i = head[u_]; i; i = ne[i]) {
    int v_ = v[i];
    if (v_ == fa_) continue;
    if (v_ != maxl[u_][0].second) Dfs2(v_, u_, maxl[u_][0].first + a[u_]);
    else Dfs2(v_, u_, maxl[u_][1].first + a[u_]);
  }
}
int F(int u_, int fa_) {
  if (f[u_].count(fa_)) return f[u_][fa_];
  int p1 = 0; 
  while (maxl[u_][p1].second == fa_) ++ p1;
	int p2 = p1 + 1; 
  while (maxl[u_][p2].second == fa_) ++ p2;

	int ret = maxl[u_][p1].first + maxl[u_][p2].first + a[u_];
  for (int i = head[u_]; i; i = ne[i]) {
    int v_ = v[i];
    if (v_ == fa_) continue;
    ret = std::max(ret, F(v_, u_));
  }
  f[u_][fa_] = ret;
  return ret;
}
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  std::cin >> n;
  for (int i = 1; i <= n; ++ i) std::cin >> a[i];
  for (int i = 1; i < n; ++ i) {
    int u_, v_; std::cin >> u_ >> v_;
    Add(u_, v_), Add(v_, u_);
  }
  Dfs1(1, 0), Dfs2(1, 0, 0);
  for (int i = 1; i <= n; ++ i) {
    int sum = 0;
    for (int j = 0; j < 4; ++ j) sum += maxl[i][j].first;
    ans = std::max(ans, sum);
  }
  for (int u_ = 1; u_ <= n; ++ u_) {
    for (int i = head[u_]; i; i = ne[i]) {
      ans = std::max(ans, F(u_, v[i]) + F(v[i], u_));
    }
  }
  std::cout << ans << "\n";
  return 0;
}

J

贪心，拓扑排序。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
#define pii std::pair<int,int>
#define mp std::make_pair
const int kN = 2e5 + 10;
//=============================================================
int n, m, p[kN], ans[kN];
std::vector <int> v[kN], u[kN];
std::vector <pii> interval[kN];
int into[kN], out[kN];
int l[kN], r[kN];
//=============================================================
void Init() {
  std::cin >> n >> m;
  for (int i = 1; i <= n; ++ i) {
    std::cin >> p[i];
    v[i].clear(), u[i].clear(), interval[i].clear();
    into[i] = out[i] = 0;
  }
  for (int i = 1; i <= m; ++ i) {
    int u_, v_; std::cin >> u_ >> v_;
    v[u_].push_back(v_), u[v_].push_back(u_);
    ++ into[v_], ++ out[u_];
  }
  for (int i = 1; i <= n; ++ i) {
    if (p[i] == 0) l[i] = 1, r[i] = n;
    else l[i] = p[i], r[i] = p[i];
  }
}
bool Topsort() {
  std::queue <int> q;
  int cnt = n;
  for (int i = 1; i <= n; ++ i) if (!into[i]) q.push(i);
  while (!q.empty()) {
    int u_ = q.front(); q.pop(); 
    -- cnt;
    for (auto v_: v[u_]) {
      l[v_] = std::max(l[v_], l[u_] + 1);
      if (!(-- into[v_])) q.push(v_);
    }
  }
  if (cnt) return false;

  for (int i = 1; i <= n; ++ i) if (!out[i]) q.push(i);
  while (!q.empty()) {
    int v_ = q.front(); q.pop();
    for (auto u_: u[v_]) {
      r[u_] = std::min(r[u_], r[v_] - 1);
      if (!(-- out[u_])) q.push(u_);
    }
  }
  for (int i = 1; i <= n; ++ i) if (l[i] > r[i]) return false;
  return true;
}
bool Solve() {
  std::priority_queue <pii> q;
  for (int i = 1; i <= n; ++ i) interval[l[i]].push_back(mp(-r[i], i));
  for (int i = 1; i <= n; ++ i) {
    for (auto x: interval[i]) q.push(x);
    if (q.empty() || -q.top().first < i) return false;
    ans[q.top().second] = i, q.pop();
  }
  return true;
}
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  int T; std::cin >> T;
  while (T --) {
    Init();
    if (!Topsort()) std::cout << "-1\n";
    else if (!Solve()) std::cout << "-1\n";
    else {
      for (int i = 1; i <= n; ++ i) std::cout << ans[i] << " ";
      std::cout << "\n";
    }
  }
  return 0;
}

写在最后

参考：

学到了什么：

  • E：平面集合问题，考虑将恶心的差值式子转化为好看的向量形式。
  • L：直觉贪心，小心数据范围诈骗。
  • G：带断边贡献为两棵树之和的换根 DP。

标签：std,Contest,int,LL,Guilin,kN,long,Site,maxl
From： https://www.cnblogs.com/luckyblock/p/18124448

相关文章

  • AtCoder Beginner Contest 348 A-F 题解
    A-PenaltyKickQuestion高桥将在一场足球比赛中获得\(N\)个点球。对于第\(i\)个罚球，如果\(i\)是\(3\)的倍数，他将罚球失败，否则罚球成功。请打印他罚球的结果。Solution当\(i\%3==0\)时说明能被\(3\)整除Code#include<bits/stdc++.h>usingnamespacest......
  • AtCoder Beginner Contest 348
    地址。赛时情况A、B题都很显然，C题大概推了好一会儿，最后还是做出来了。D题感觉十分难做，估计很难写，看了E。感觉还是不会，听说是原题，搜了一下，发现是树的重心，我还不会。直接贺题解，发现不对。修改了一下还是不对，最后发现INF取小了，过了。后面的不看了。赛后总结还行，跳过D......
  • AtCoder Beginner Contest 204
    E-RushHour2设函数f(t)=t+ci+di/(t+1);易得当t=sqrt(di)-1时取最小所以根据时间来做dij当时间大于sqrt(di)-1时直接加入即可同时用并查集来查看1和n是否联通即可accode：点击查看代码#include<bits/stdc++.h>#defineintlonglong#defineall(x)x.begin(),x.end()......
  • translate-your-site
    TranslateyoursiteLet'stranslatedocs/intro.mdtoFrench.Configurei18nModifydocusaurus.config.jstoaddsupportforthefrlocale:module.exports={i18n:{defaultLocale:'en',locales:['en','fr'],......
  • deploy-your-site
    DeployyoursiteDocusaurusisastatic-site-generator(alsocalledJamstack).ItbuildsyoursiteassimplestaticHTML,JavaScriptandCSSfiles.BuildyoursiteBuildyoursiteforproduction:npmrunbuildThestaticfilesaregeneratedinthebuild......
  • AtCoder Beginner Contest 348
    A-PenaltyKick(abc348A)题目大意给定\(n\)，输出\(ooxooxoox...\)，长度为\(n\)。解题思路按题意模拟即可。神奇的代码n=int(input())ans="oox"*(n//3)+"o"*(n%3)print(ans)B-FarthestPoint(abc348B)题目大意给定\(n\)个点，对每个点，求出与其......
  • AISing Programming Contest 2021（AtCoder Beginner Contest 202）
    D-aabababaa根据题意从左往右进行分析如果当前该字母为a那么存在两种情况一种为b的数量为0一种为剩余的k的数量小于右边所有情况的总和其总和对应为C(剩余的长度,b的个数)反之则为b点击查看代码intget(intx,inty){intans=1;for(inti=1;i<=y;i++){ans=(x-i......
  • AtCoder Beginner Contest 347 A~F
    AtCoderBeginnerContest347A~F-知乎(zhihu.com)Tasks-AtCoderBeginnerContest347A.Divisible(循环)代码#include<bits/stdc++.h>usingnamespacestd;voidsolve(){intn,k;cin>>n>>k;for(inti=0;i<n;i++){......
  • KYOCERA Programming Contest 2021（AtCoder Beginner Contest 200）
    题目链接https://atcoder.jp/contests/abc200A-Century简单的abs(n-1)/100+1即可B-200thABC-200按题意写代码点击查看代码voidsolve(){intn,k;cin>>n>>k;for(inti=1;i<=k;i++){if(n%200==0)n/=200;elsen=n*1000+200;}......
  • Where to Go Next for Recommender Systems? ID- vs. Modality-based Recommender Mod
    目录概符号/缩写说明TrainingdetailsDatasetsE2E下MoRec是否优于IDRec?RegularsettingWarmsetting越好的encoder带来越好的推荐效果?TSversusE2E?总结代码YuanZ.,YuanF.,SongY.,LiY.,FuJ.,YangF.,PanY.andNiY.Wheretogonextforrecommendersys......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99