首页 > 其他分享 >The 19th Zhejiang Provincial Collegiate Programming Contest

The 19th Zhejiang Provincial Collegiate Programming Contest

时间：2024-03-28 23:58:08浏览次数：30  
标签：std Provincial Contest int LL Programming kN long include

目录

写在前面

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

以下按照个人向难度排序

Just a Way 闪击珞珈之初次合作。

理应能 7 题，但是赛时开局罚烂中期烂了两题导致后面的没法写被迫五题下班妈的

唉牢鱼想你了

C

纯签到，建议评级：200

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
//=============================================================
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  int n, m, x, cnt = 0;
  std::cin >> n >> m >> x;
  for (int i = 1; i <= n; ++ i) {
    int a; std::cin >> a;
    if (a >= x) ++ cnt;
  }
  for (int i = 1; i <= m; ++ i) {
    int b; std::cin >> b;
    if (b <= x) ++ cnt;
  }
  std::cout << cnt << "\n";
  return 0;
}

B

纯签到，建议评级：300

Code by dztle：

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
	int x=0,f=1; char s;
	while((s=getchar())<'0'||s>'9') if(s=='-') f=-1;
	while(s>='0'&&s<='9') x=(x*10)+(s^'0'),s=getchar();
	return x*f;
}
char name[200005];
char ans[200005];
signed main(){
	scanf("%s",name);
	int len=strlen(name);
	int now=0;
	for(int i=0;i<len;++i){
		ans[++now]=name[i];
		if(i>=2){
			if(name[i]=='b'&&name[i-1]=='j'&&name[i-2]=='c'){
				ans[++now]=',';
			}
		}
	}	
	for(int i=1;i<=now;++i){
		cout<<ans[i];
	}
	return 0;
}

A

大力特判。

  • \(a=b\)：答案为 0。
  • \(a>b\)：若 \(2 | a-b\) 答案为 1，否则答案为 2（先操作 1 后操作 2 ）。
  • \(a<b\)：若 \(2 \not| b-a\) 答案为 1，否则若 \(2 \not| \frac{b-a}{2}\) 答案为 2（两次操作 1），否则答案为 3（两次操作 1 一次操作 2）。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
//=============================================================
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  // std::ios::sync_with_stdio(0), std::cin.tie(0);
  int T; std::cin >> T;
  while (T --) {
    int a, b; std::cin >> a >> b;
    if (a == b) std::cout << 0 << "\n";
    else if (b - a > 0) {
      if ((b - a) % 2 == 1) std::cout << 1 << "\n";
      else if (((b - a) / 2) % 2 == 1) std::cout << 2 << "\n";
      else std::cout << 3 << "\n";
    } else {
      if ((a - b) % 2 == 0) std::cout << 1 << "\n";
      else std::cout << 2 << "\n";
    }
  }
  return 0;
}

L

双指针。

考虑在限制平均值不大于 \(K\) 的情况下应当如何选数。显然所有小于 \(K\) 的数均可选择，对于大于 \(K\) 的数应当尽可能选择其中较小的。

则选择的数集一定是排序后数列的一段前缀，考虑枚举前缀计算平均值，双指针求解不大于平均值的数的个数即得该前缀的贡献。

总时间复杂度 \(O(n)\) 级别。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e6 + 10;
//=============================================================
int n, ans, a[kN];
LL sum;
//=============================================================
//=============================================================
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];
  std::sort(a + 1, a + n + 1);

  for (int i = 1, maxp = 1; i <= n; ++ i) {
    sum += a[i];
    while (maxp < i && 1ll * i * a[maxp] <= sum) ++ maxp;
    ans = std::max(ans, i - maxp + 1);
  }
  std::cout << ans << "\n";
  return 0;
}

M

数学。

妈的诈骗题，骗得我去写 300 行的字符串匹配最后挂成狗

保证给出的图形均为合法图形且互不重叠，且发现仅有两种图形，于是考虑统计给定图形中的黑色位置数量与空洞的数量，即可解方程得到两种图形数量。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1010;
const char hole[8][8] = {
  "######",
  "##..##",
  "#....#",
  "#....#",
  "##..##",
  "######"
};
//=============================================================
std::string s[kN];
int n, m, a, b, x, y;
//=============================================================
bool check(int x0_, int y0_, int x1_, int y1_) {
  if (x0_ < 0 || y0_ < 0) return false;
  for (int i = x0_, p = 0; i <= x1_; ++ i, ++ p) {
    for (int j = y0_, q = 0; j <= y1_; ++ j, ++ q) {
      if (s[i][j] != hole[p][q]) return false;
    }
  }
  return true;
}
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  std::cin >> n >> m;
  for (int i = 0; i < n; ++ i) {
    std::cin >> s[i];
    for (auto ch: s[i]) a += (ch == '#');
  }
  for (int i = 0; i < n; ++ i) {
    for (int j = 0; j < m; ++ j) {
      if (check(i - 5, j - 5, i, j)) ++ b;
    }
  }
  // 146x + 100y = a
  // 2x + y = b

  //200x + 100y = 100b
  //54x = 100b - a

  x = (100 * b - a) / 54;
  y = b - 2 * x;
  std::cout << x << " " << y << "\n";
  return 0;
}

G

在起点终点与关键点之间建图最短路。

注意是稠密图，朴素 Dijkstra 运行效率更高。

Code by hjxddl，赛时还是写了堆优化:

#include<cstdio>
#include<iostream>
#include<algorithm> 
#include<bitset>
#include<vector>
#include<cmath>
#include<queue>
#define ll long long
#define db long double
using namespace std;
const int N=1e3+5;
const db eps=1e-9;
struct node{
	db x,y;
}p[N];
db v1,v2;
bitset<N>vis;
db dis[N];
vector<pair<int,db>>e[N];
db diss(int a,int b){
	return sqrt((p[a].x-p[b].x)*(p[a].x-p[b].x)+(p[a].y-p[b].y)*(p[a].y-p[b].y));
}
db cult(int x,int y){
	db dis=diss(x,y);
	if(!x)
		return dis/v1;
	if(dis-3.0*v2<=eps)
		return dis/v2;
	return 3.0+(dis-(v2*3.0))/v1;
}
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		scanf("%Lf%Lf",&p[i].x,&p[i].y);
	scanf("%Lf%Lf%Lf%Lf",&p[0].x,&p[0].y,&p[n+1].x,&p[n+1].y);
	scanf("%Lf%Lf",&v1,&v2);
	for(int i=0;i<=n;i++){
		for(int j=1;j<=n+1;j++){
			if(i==j)continue;
			e[i].emplace_back(j,cult(i,j));
		}
	}
	priority_queue<pair<db,int>>q;
	for(int i=0;i<=n+1;i++)
		dis[i]=1e18;
	q.push({0,0});
	dis[0]=0;
	while(q.size()){
		int x=q.top().second;
		q.pop();
		if(vis[x])continue;
		vis[x]=1;	
		for(auto [y,z]:e[x]){
			if(dis[y]-dis[x]-z>eps){
				dis[y]=dis[x]+z;
				q.push({-dis[y],y});
			}
		}
	}
	printf("%.9Lf\n",dis[n+1]);
}

I

结论。

赛时想到关键结论了但是就差一步没敢继续往下想妈的也可能是烂题了摆了

对于一次询问的子串，若初始即为回文串则先手必败。否则定义删去左右两端之一后为回文串的字符串为先手必败态，发现这样的字符串一定为如下字符 ab 交替的形式：

\[\underline{\text{a}}\underline{\underline{\text{bab}\cdots \text{baba}} \text{b}} \]

发现这样的字符串一定长度为偶数（包括仅有两个字符的情况），则可知此时胜负状态仅与字符串的奇偶性有关。

判断回文串使用哈希则每次询问均可 \(O(1)\) 地回答，则总时间复杂度 \(O(n + q)\) 级别。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const LL p1 = 998244353;
const LL c1 = 114514;
const int kN = 1e6 + 10;
//=============================================================
int n, q;
char s[kN], t[kN];
LL pow1[kN], hs[kN], ht[kN];
//=============================================================
LL hash1(LL *h_, int l_, int r_) {
  return (h_[r_] - pow1[r_ - l_ + 1] * h_[l_ - 1] % p1 + p1) % p1;
}
bool is_palindrome(int l_, int r_) {
  return hash1(hs, l_, r_) == hash1(ht, n - r_ + 1, n - l_ + 1);
}
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  // std::ios::sync_with_stdio(0), std::cin.tie(0);
  scanf("%d%d", &n, &q);
  scanf("%s", s + 1);
  for (int i = 1, j = n; i <= n; ++ i, -- j) t[i] = s[j];

  pow1[0] = 1;
  for (int i = 1; i <= n; ++ i) {
    pow1[i] = pow1[i - 1] * c1 % p1;
    hs[i] = (c1 * hs[i - 1] + s[i]) % p1;
    ht[i] = (c1 * ht[i - 1] + t[i]) % p1;
  }

  while (q --) {
    int l, r; scanf("%d%d", &l, &r);
    if (is_palindrome(l, r)) printf("Budada\n");
    else printf("%s\n", ((r - l + 1) % 2 == 1) ? "Putata" : "Budada");
  }
  return 0;
}
/*
7 3
potatop
1 2
*/

F

二维数点，讨论。

赛时讨论了下就会了然而没空写唉

考虑对于一次交换操作 \((l, r)\)，哪些位置的 C 会受到影响：

  • 对于 \(p_1\sim p_{l - 1}\)，\(p_{r + 1}\sim p_n\)：无影响。
  • 对于 \(p_l, p_r\)：考虑主席树维护区间的数的种类数，直接动态地重新求 C 即可。
  • 对于 \(p_{l + 1}\sim p_{r - 1}\)：
    • 仅会影响其中满足 \(p_l < p_i < p_r\) 的位置，且影响至多为 1。
    • 当 \(p_l < p_r\) 时导致 \(A_i-1, B_i+1\)，\(p_l > p_r\) 时导致 \(A_i + 1, B_i - 1\)：
    • 对于满足 \(|A_i - B_i| > 1\) 的位置 \(i\)，交换后 \(C_i = \min(A_i, B_i)\) 中较小的一方不变。
    • 对于满足 \(|A_i - B_i| = 1\) 的位置 \(i\)，交换后 \(C_i = \min(A_i, B_i)\) 的值要么不变要么减 1。
    • 对于满足 \(A_i = B_i\) 的位置 \(i\)，交换后必定 \(C_i\) 减 1。
    • 于是考虑主席树维护区间中上述各种位置的数量，根据 \(p_l, p_r\) 的大小情况讨论影响即可。

考虑对原排列主席树维护上述各种位置的数量，每次询问按照上述过程进行讨论即可得到 \(\sum C_i\) 的改变量，实现详见代码注释。

每次询问会调用常数次主席树的区间查询，则总时间复杂度为 \(O((n + m)\log n)\) 级别。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e5 + 10;
//=============================================================
int n, m, p[kN];
int rt[kN];
LL sumc[kN];
//=============================================================
namespace Hjt {
  #define ls lson[now_]
  #define rs rson[now_]
  #define mid ((L_+R_)>>1)
  const int kNode = kN << 5;
  int nodenum, lson[kNode], rson[kNode];
  LL sz[kNode][6];
  //0：所有数量
  //1：C=A 且差 > 1 的数量
  //2：C=B 且差 > 1 的数量
  //3：C=A 且差 = 1 的数量
  //4：C=B 且差 = 1 的数量
  //5：A=B 的数量
  void Insert(int &now_, int pre_, int L_, int R_, int pos_, int type_) {
    now_ = ++ nodenum;
    sz[now_][0] = sz[pre_][0] + 1;
    for (int i = 1; i <= 5; ++ i) {
      sz[now_][i] = sz[pre_][i] + (type_ == i);  
    }
    if (L_ == R_) return ;

    ls = lson[pre_], rs = rson[pre_];
    if (pos_ <= mid) Insert(ls, ls, L_, mid, pos_, type_);
    else Insert(rs, rs, mid + 1, R_, pos_, type_);
  }
  int Query(int lnow_, int rnow_, int L_, int R_, int l_, int r_, int type_) {
    if (l_ <= L_ && R_ <= r_) return sz[rnow_][type_] - sz[lnow_][type_];
    int ret = 0;
    if (l_ <= mid) ret += Query(lson[lnow_], lson[rnow_], L_, mid, l_, r_, type_);
    if (r_ > mid) ret += Query(rson[lnow_], rson[rnow_], mid + 1, R_, l_, r_, type_);
    return ret;
  }
  #undef ls
  #undef rs
  #undef mid
}
//=============================================================
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 >> p[i];
    LL A = Hjt::Query(rt[0], rt[i - 1], 1, n, 1, p[i], 0);
    LL B = p[i] - 1 - A, type = 0;
    sumc[i] = sumc[i - 1] + std::min(A, B);

    if (A == B) type = 5;
    else if (std::max(A, B) - std::min(A, B) == 1) type = (A < B) ? 3 : 4;
    else type = (A < B) ? 1 : 2;
    Hjt::Insert(rt[i], rt[i - 1], 1, n, p[i], type);
  }

  std::cin >> m;
  while (m --) {
    int l, r; std::cin >> l >> r;
    if (l > r) std::swap(l, r);
    int vmin = std::min(p[l], p[r]) + 1, vmax = std::max(p[l], p[r]) - 1;
    LL sz[6] = {0}, delta = -(sumc[r] - sumc[r - 1]) - (sumc[l] - sumc[l - 1]);
  
    int A = Hjt::Query(rt[0], rt[l - 1], 1, n, 1, p[r], 0);
    int B = p[r] - 1 - A;
    delta += std::min(A, B);
    B = Hjt::Query(rt[r], rt[n], 1, n, 1, p[l], 0);
    A = p[l] - 1 - B;
    delta += std::min(A, B);

    if (vmin <= vmax) {
      for (int i = 1; i <= 5; ++ i) {
        sz[i] = Hjt::Query(rt[l - 1], rt[r], 1, n, vmin, vmax, i);
      }
      if (p[l] < p[r]) { //令A-1, B+1
        delta += -sz[1] + sz[2] - sz[3] - sz[5];
      } else {
        delta += sz[1] - sz[2] - sz[4] - sz[5];
      }
    }
    
    std::cout << sumc[n] + delta << "\n";
  }
  return 0;
}

J

咕咕，上课在写。

写在最后

学到了什么：

  • M：发现某些地方奇小可能有特殊的乱搞。
  • G：稠密图堆朴素 Dijkstra 跑得更好。
  • I：用字符串中某些位置相等的特性进行推导，一般可以推导出特殊的字符串形态。
  • 卡题了让队友看看，换个思路。

想你了牢鱼唉

标签：std,Provincial,Contest,int,LL,Programming,kN,long,include
From： https://www.cnblogs.com/luckyblock/p/18102893

相关文章

  • AtCoder Beginner Contest 346
    AtCoderBeginnerContest346比赛链接A-AdjacentProduct思路：b[i]=a[i]*a[i+1]Code#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#defineall(x)x.begin()+1,x.end()voidsolve(){ intn; cin>>n; std::vector<in......
  • UNIQUE VISION Programming Contest 2024 Spring(AtCoder Beginner Contest 346)
    C我们用\(1\simK\)的和减去出现在\(1\simK\)中的数的和。intn,k,a[N],res;map<int,int>vis;signedmain(){ cin>>n>>k; _for(i,1,n)cin>>a[i]; res=k*(1+k)/2; _for(i,1,n)if(a[i]>=1&&a[i]<=......
  • AtCoder Regular Contest 173 E Rearrange and Adjacent XOR
    洛谷传送门AtCoder传送门不妨考虑最后的结果可以成为哪些\(a_i\)的组合。为了方便分析，我们令\(a_i=2^{i-1}\)。进行一次操作后，所有\(\text{popcount}(a_i)\)都为偶数。所以一个\(x\in[0,2^n-1]\)能被生成出来的必要条件是\(\text{popcount}(x)\)为偶数。然......
  • AtCoder Beginner Contest 346 (ABCDEF)
    AtCoderBeginnerContest346A-AdjacentProduct题意给你一个数组a1,a......
  • AtCoder Beginner Contest 346 题解
    A-AdjacentProductQuestion给你\(N\)个整数\(A_1,A_2,\dots,A_N\)。同时，定义\(B_i=A_i\timesA_{i+1}\(1\leqi\leqN-1)\)按此顺序打印\(B_1,B_2,\dots,B_{N-1}\)Solution按照题意模拟Code#include<bits/stdc++.h>usingnamespacestd;intmain......
  • Weekly Contest 390
    ProblemA每个字符最多出现两次的最长子字符串思路双指针，使用一个数组记录每个字符的出现次数，当出现次数大于2时l往左收缩其余情况往右划代码classSolution{publicintmaximumLengthSubstring(Strings){intn=s.length();int[]cnt=newint......
  • Programming Abstractions in C阅读笔记：p338-p346
    《ProgrammingAbstractionsinC》学习第80天，p338-p346，总计9页。一、技术总结栈的实现包括入栈、出栈、判断栈是否为满，判断栈是否为空等。作者结合RPN计算器来实现，稍显无聊。/**File:rpncalc.c*---------------*Thisprogramsimulatesanelectroniccalculatorth......
  • AtCoder Beginner Contest 346
    AtCoderBeginnerContest346最刺激的一集。尝试挑战手速极限，用了57s做A。但是好像还是很慢。然后做B，仍然想挑战手速。结果一眼出思路只要把wbwbwwbwbwbw多重复几遍就可以代替「无限长」。很快就写完了。然后交了三发罚时。后来发现我复制若干遍wbwbwwbwbwbw的时候......
  • AtCoder Beginner Contest 346
    A-AdjacentProduct(abc346A)题目大意给定\(n\)个数，依次输出相邻俩数的乘积。解题思路按照题意模拟即可。神奇的代码#include<bits/stdc++.h>usingnamespacestd;usingLL=longlong;intmain(void){ios::sync_with_stdio(false);cin.tie(0);c......
  • 『The Go Programming Language』二、程序结构
    2.1名称名称开头通常为字母或下划线且区分大小写。存在25个关键字只能用于合法处不能用作名称：breakdefaultfuncinterfaceselectcasedefergomapstructchanelsegotopackageswitchconstfallthroughifrangetypecontinueforimportreturnvar此外还存在预声明的常量、类型和函......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99