首页 > 其他分享 >The 2022 ICPC Asia Xian Regional Contest

The 2022 ICPC Asia Xian Regional Contest

时间：2024-09-18 16:37:41浏览次数：1  
标签：std Contest int LL Regional Xian kN long operatorname

目录

写在前面

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

以下按个人向难度排序。

vp 8 题 900+ 罚时差 100 罚时金。

唉唉现在题数够了还是很爽的，然而唐氏太多白白吃好多发不该。

而且感觉队友在线时长不够啊呃呃必须要 push 一下、、、

F 签到

祝大秦酒店越办越好。

不对我草今年估计 EC 西安应该能拿个名额怎么轮到我去住大秦酒店了我草

Code by wenqizhi：

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

#define ll long long
#define ull unsigned long long

int read()
{
    int x = 0; bool f = false; char c = getchar();
    while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
    while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

const int N = 1000;
int n, c1, c2;
char s[100];
int main()
{
    n = read(), c1 = read(), c2 = read(), c1 = min(c1, c2);
    if(c1 * 2 <= c2){ printf("%lld\n", 3ll * n * c1); return 0; }
    ll ans = 0;
    for(int i = 1; i <= n; ++i)
    {
        scanf("%s", s + 1);
        int flag = 0;
        if(s[1] == s[2] || s[1] == s[3] || s[2] == s[3]) flag = 1;
        if(flag) ans += c1 + c2;
        else ans += c1 * 3;
    }
    printf("%lld\n", ans);
    return 0;
}

J 签到

考虑枚举选的数中下标 \(i\) 的最大值，发现之后仅能在 \(1\sim i-1\) 中再选一个数，优先队列搞一下即可。

//
/*
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; std::cin >> n;
  std::priority_queue <int> q;
  
  LL ans = 0;
  for (int i = 1; i <= n; ++ i) {
    int a; std::cin >> a;
    LL sum = a;
    if (!q.empty()) sum += std::max(0, q.top());
    ans = std::max(ans, sum);
    q.push(a);
  }
  std::cout << ans << "\n";
  return 0;
}

C 贪心，模拟

发现所有人先进行复制再进行造题一定是最优的，若某轮中既有造题的又有复制的，将这轮都改成复制，则最终结束时刻一定不会更靠后。

复制时数量是倍增的，于是直接枚举复制几轮即可。

Code by dztlb：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
const int inf=1e9;
int T;
int a,b,c;
signed main(){
	cin>>T;
	while(T--){
		cin>>a>>b>>c;
		int ans=inf*inf;
		for(int i=0;i<=30;++i){
			int cnt=1;
			int tmp=0;
			for(int j=1;j<=i;++j){
				cnt*=2;
				tmp+=a;
			}
			int now=(c/cnt);
			if(c%cnt!=0) ++now;
			tmp+=now*b;
			ans=min(ans,tmp);
		}
		cout<<ans<<'\n';
	}
	return 0;
}

G 字符串，哈希

显然答案一定是给定的 \(n\) 个字符串中的某个。

答案 \(s_1s_2\cdots s_{|s|}\) 的所有子串均在给定的 \(n\) 个字符串中出现过，发现这等价于：\(s_2s_2\cdots s_{|s|}\) 与 \(s_1s_2\cdots s_{|s|-1}\) 均出现过。

于是考虑把所有字符串哈希一下用于判重，然后按照长度枚举所有字符串，通过上述结论判断当前字符串是否合法并标记即可。

被标记的最长的字符串即为答案。

有唐氏写哈希忘驱魔了呃呃

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e5 + 10;
const LL p = 1e9 + 7;
const LL c = 1331;
//=============================================================
int n;
std::string s[kN];
bool yes[kN];
std::set<LL> hash;
//=============================================================
bool cmp(const std::string &fir_, const std::string &sec_) {
  return fir_.length() < sec_.length();
}
//=============================================================
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 >> s[i];
  std::sort(s + 1, s + n + 1, cmp);

  int ans = 0;
  for (int i = 1; i <= n; ++ i) {
    int len = s[i].length();
    LL h = 0, h1 = 0, h2 = 0;
    if (len == 1) {
      yes[i] = 1;
    } else {
      for (int j = 0; j < len - 1; ++ j) h1 = (c * h1 + s[i][j]) % p;
      for (int j = 1; j < len; ++ j) h2 = (c * h2 + s[i][j]) % p;
      yes[i] = (hash.count(h1) && hash.count(h2));
    }
    h = (c * h1 + s[i][len - 1]) % p;
    if (yes[i]) ans = std::max(ans, len), hash.insert(h);
  }
  std::cout << ans << "\n";
  return 0;
}
/*
5
a
aa
aaa
aaaa
aaaaa
*/

L 贪心，结论

有唐氏写的一坨嗯吃两发被我狠狠批判然后五分钟重构一发过了。

题意等价于使用极大的链或反链完全覆盖一棵有根树的最小覆盖次数。

发现若使用反链进行覆盖，最优的情况是每次选择当前有根树的所有叶节点。若不覆盖叶节点则既不能减少链的数量，从而便于使用链覆盖，且之后不可避免地还需要覆盖叶节点。

叶节点至多仅有 \(O(n)\) 层，于是考虑模拟地不断使用反链覆盖，枚举删去叶节点的层数，则之后需要的链覆盖的次数即为当前叶节点数量。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e6 + 10;
//=============================================================
std::vector<int> leaves[2];
int n, fa[kN], son[kN];
//=============================================================
//=============================================================
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 >> n;
    leaves[0].clear(), leaves[1].clear();
    for (int i = 1; i <= n; ++ i) son[i] = fa[i] = 0;
    for (int i = 2; i <= n; ++ i) {
      std::cin >> fa[i];
      ++ son[fa[i]];
    }
    
    for (int i = 1; i <= n; ++ i) {
      if (son[i] == 0) leaves[0].push_back(i);
    }

    int ans = leaves[0].size(), now = 0;
    for (int i = 1; i <= n; ++ i, now ^= 1) {
      if (leaves[now].empty()) break;
      leaves[now ^ 1].clear();

      for (auto u: leaves[now]) {
        -- son[fa[u]];
        if (son[fa[u]] == 0) leaves[now ^ 1].push_back(fa[u]);
      }
      ans = std::min(ans, (int) (i + leaves[now ^ 1].size()));
    }
    std::cout << ans << "\n";
  }
  return 0;
}
/*
3
7
1 1 2 2 2 3
5
1 2 3 4
11
1 2 3 4 5 2 3 4 5 6
*/

E 数学，模拟

发现给定式子相当于考虑 \(x\) 的三进制表示，\(f(x)\) 即三进制下的位数+三进制各位之和。

于是大力讨论即可。最优情况是各位全部取 2，需要讨论被上下界限制时取不到最优情况。

Code by wenqizhi：

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

#define ll long long
#define ull unsigned long long

ll read()
{
    ll x = 0; bool f = false; char c = getchar();
    while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
    while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

const int N = 105;
ll sum[N];

void init()
{
    sum[0] = 1;
    for(int i = 1; i; ++i)
    {
        sum[i] = sum[i - 1] * 3;
        if(sum[i] > 1e18) break;
    }
}

int get(int len, ll r)
{
    ll L = sum[len - 1];
    int cnt = 1;
    for(int i = 1; i <= len; ++i)
    {
        for(int j = 1; j <= 2 - (i == len); ++j)
            if(sum[i - 1] + L <= r) ++cnt, L += sum[i - 1];
    }
    return cnt;
}

void solve()
{
    ll l = read(), r = read(), L = l;
    int ans = 0;
    int len = 0, cnt = 0;
    while(L)
    {
        cnt += L % 3;
        L /= 3;
        ++len;
    }
    L = l;
    len = max(len, 1);
    ans = max(ans, cnt);
    for(int i = 1; i <= len; ++i)
    {
        int res = 3 - l / sum[i - 1] % 3 - 1;
        for(int j = 1; j <= res; ++j)
            if(sum[i - 1] + L <= r) ++cnt, L += sum[i - 1];
    }
    ans = max(ans, cnt + len);
    for(int i = len + 1; i; ++i)
    {
        if(sum[i - 1] > r || sum[i - 1] == 0) break;
        ans = max(ans, get(i, r) + i);
    }
    printf("%d\n", ans);
}

int main()
{
    init();
    int T = read();
    while(T--) solve();
    return 0;
}

B 结论，网络流

我去这题给 dztlb 大神开出来了真是我叠吧

根据给定的变量的含义，颜色数量 \(k\) 与填 0 数量 \(z\) 显然成反比关系，则容易看出 \(ck+dz\) 是关于 \(k\) 的单谷函数。于是考虑三分，检查在使用 \(k\) 种颜色情况下，最少填多少 0（最多可以填多少非 0）可以合法，即可求得对应的 \(ck+dz\) 的值。

发现问题可以看做是在给定颜色种类数限制下，保证每行/每列同种非 0 颜色数量不大于 1，最大化填的非 0 的数量，又数据范围很小，一个显然的想法是通过网络流进行非 0 的填色最大化流量，跑最大流即为所求。

对于上述问题，记三分量为 \(\operatorname{mid}\)，dztlb 大神的建图策略如下：

  • 先统计每行/每列的空格数量，记为 \(\operatorname{cntx}, \operatorname{cnty}\)；
  • 对每行/每列建点，编号分别为 \(1\sim n\)，\(n + 1\sim n + m\)；
  • 对于第 \(i\) 行，若有 \(\operatorname{cntx}_i\ge \operatorname{mid}\)，连边 \((S, i, \operatorname{cntx}_i - \operatorname{mid})\)，然后枚举列 \(j\)，若有 \(\operatorname{cnty}_j\ge \operatorname{mid}\)，连边 \((i, n+j, 1)\)；
  • 对于第 \(j\) 列，若有 \(\operatorname{cnty}_j\ge \operatorname{mid}\)，连边 \((n+j, T, \operatorname{cnty}_j - \operatorname{mid})\)；
  • 则最小化填 0 数量即：\(\sum \operatorname{cntx} + \sum \operatorname{cnty} - \operatorname{maxflow}\)。

建边数量为 \(O(nm)\) 级别，但是这图只有 4 层根本跑不满，实际运行效率非常高。

然后我当代码黑奴给 dztlb 大神写了最大流写了三分就过了哈哈

//知识点：网络最大流，Dinic
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e5 + 10;
const int kM = 2e6 + 10;
const LL kInf = 1e18 + 2077;
//=============================================================
int n, m, c, d, S, T;
int nodenum, maxnodenum, edgenum = 1, v[kM], ne[kM], head[kN];
int cur[kN], dep[kN];
std::string map[kN];
int cn[kN],cm[kN];
LL w[kM];
//=============================================================
void addedge(int u_, int v_, LL w_) {
  v[++ edgenum] = v_;
  w[edgenum] = w_;
  ne[edgenum] = head[u_];
  head[u_] = edgenum;

  v[++ edgenum] = u_;
  w[edgenum] = 0;
  ne[edgenum] = head[v_];
  head[v_] = edgenum;
}
void init() {
  edgenum = 1;
  nodenum = n + m;
  maxnodenum = 3 * n + 2;
  S = ++ nodenum, T = ++ nodenum;
  
  for (int i = 1; i <= maxnodenum; ++ i) {
    head[i] = 0;
  }
}
bool bfs() {
  std::queue <int> q;
  memset(dep, 0, (nodenum + 1) * sizeof (int));
  dep[S] = 1; //注意初始化 
  q.push(S); 
  while (!q.empty()) {
    int u_ = q.front(); q.pop();
    for (int i = head[u_]; i > 1; i = ne[i]) {
      int v_ = v[i], w_ = w[i];
      if (w_ > 0 && !dep[v_]) {
        dep[v_] = dep[u_] + 1;
        q.push(v_);
      }
    }
  }
  return dep[T];
}
LL dfs1(int u_, LL into_) {
  if (u_ == T) return into_; 
  LL ret = 0;
    for (int i = cur[u_]; i > 1 && into_; i = ne[i]) {
    int v_ = v[i];
    LL w_ = w[i];
    if (w_ && dep[v_] == dep[u_] + 1) {
            LL dist = dfs1(v_, std::min(into_, w_));
            if (!dist) dep[v_] = kN;
            into_ -= dist; 
      ret += dist;
      w[i] -= dist, w[i ^ 1] += dist;
            if (!into_) return ret;
        }
  }
    if (!ret) dep[u_] = 0; 
  return ret;
}
LL dinic() {
  LL ret = 0;
  while (bfs()) {
    memcpy(cur, head, (nodenum + 1) * sizeof (int));
    ret += dfs1(S, kInf);
  }
  return ret;
}
LL check(LL mid_) {
  init();
  LL tmp=0;
	for(int i=1;i<=n;++i){
		if(cn[i]>mid_){
			addedge(S,i,cn[i]-mid_);
			tmp+=cn[i]-mid_;
			for(int j=1;j<=m;++j){
				if(cm[j]>mid_){
					addedge(i,n+j,1);
				}
			}
		}
	}
  for(int i=1;i<=m;++i){
		if(cm[i]>mid_){
			addedge(n+i,T,cm[i]-mid_);
			tmp+=cm[i]-mid_;
		}
	}
	return 1ll * mid_ * c + d * (tmp - dinic());
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  std::cin >> n >> m >> c >> d;
  for (int i = 1; i <= n; ++ i) {
    std::cin >> map[i]; map[i] = "$" + map[i];
  }
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(map[i][j]=='.'){
				cn[i]++,cm[j]++;
			}
		}
	}

  LL lmid, rmid, lans = kInf, rans = kInf;
  for (LL l = 0, r = std::max(n, m); l <= r; ) {
    lmid = l + (r - l) / 3;
    rmid = r - (r - l) / 3;
    lans = check(lmid), rans = check(rmid);
    if (rans <= lans) l = lmid + 1;
    else r = rmid - 1;
  }
  std::cout << std::min(lans, rans) << "\n";
  return 0;
}
/*
5 5 3 1
*..*.
...**
.*...
..*..
..*..
*/

A LCT or 根号预处理 or 线段树分治维护连通性

我去这题给我开出来了最后十分钟一发过了我真是叠吧

保证一个点至多连一条桥，则从每个起点出发，到达的终点一定是不同且唯一的。

发现在 \((a, b), (a + 1, b)\) 连边，对移动路径的影响，等价于断开边：\((a, b)\rightarrow (a, b + 1), (a+1, b)\rightarrow (a+1, b + 1)\)，然后连边：\((a, b)\rightarrow (a+1, b + 1), (a+1, b)\rightarrow (a, b + 1)\)。

发现断边连边后，给定的图仍是 \(n\) 条长度为 \(m+1\) 的链，一个显然的想法是使用 LCT 直接维护，考虑仅令每条链结尾的点权值为其链号，则查询仅需查询给定起点对应链的树的权值和即可。

然而有 \(O(nm)\) 个点并不能直接做，但是发现至多只有 \(q\) 次操作，则有影响的点仅有 \(O(n+q)\) 级别，于是考虑将每行的点按是否连了桥进行分段，则每段都可以直接缩成一个点考虑，就能直接上 LCT 了。

我的分段缩点方法是先将每条链看做一个点，然后模拟连桥后将原来的点分裂得到新点，比较唐呃呃，优美做法可见 HolyK 的这发提交：https://codeforces.com/gym/104077/submission/183684508。

std 是根号预处理；此外还有大神的线段树分治维护连通性，可见这发提交：https://codeforces.com/gym/104077/submission/272665032。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
#define pr std::pair
#define mp std::make_pair
const int kN = 5e5 + 10;
//=============================================================
int n, m, q, a[kN], ans[kN];
struct O {
  int opt, a, b;
} op[kN];
struct Node {
  int id, a, l, r, val;
  bool operator <(const Node& sec_) const {
    if (a != sec_.a) return a < sec_.a;
    if (r != sec_.r) return r < sec_.r;
    if (l != sec_.l) return l < sec_.l;
    if (id != sec_.id) return id < sec_.id;
    return val < sec_.val;
  } 
} node[kN];
int nodenum, next[kN];
std::set<Node> st;
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
namespace LCT {
  #define f fa[now_]
  #define ls son[now_][0]
  #define rs son[now_][1]
  int fa[kN], son[kN][2];
  int val[kN], sum[kN], sum1[kN];
  bool rev[kN];

  void clear(int now_) {
    ls = rs = f = val[now_] = 0;
  }
  void Pushup(int now_) {
    sum[now_] = (sum[ls] + sum[rs] + val[now_] + sum1[now_]);
  }
  void Rev(int now_) {
    if (!now_) return ;
    std::swap(ls, rs);
    rev[now_] ^= 1;
  }
  void Pushdown(int now_) {
    bool rev_ = rev[now_];
    if (rev_) Rev(ls), Rev(rs);
    rev[now_] = 0;
  }
  bool Isroot(int now_) {
    return son[f][0] != now_ && son[f][1] != now_;
  }
  bool Whichson(int now_) {
    return son[f][1] == now_;
  }
  void Rotate(int now_) {
    int fa_ = f, ffa = fa[f], w = Whichson(now_);
    if (!Isroot(f)) son[fa[f]][Whichson(f)] = now_;
    f = fa[f];

    son[fa_][w] = son[now_][w ^ 1];
    fa[son[fa_][w]] = fa_;

    son[now_][w ^ 1] = fa_;
    fa[fa_] = now_;
    Pushup(fa_), Pushup(now_), Pushup(ffa);
  }
  void Update(int now_) {
    if (!Isroot(now_)) Update(f);
    Pushdown(now_);
  }
  void Splay(int now_) {
    Update(now_);
    for (; !Isroot(now_); Rotate(now_)) {
      if (!Isroot(f)) Rotate(Whichson(f) == Whichson(now_) ? f : now_);
    }
  }

  void Access(int now_) {
    for (int last = 0; now_; last = now_, now_ = f) {
      Splay(now_); 
      sum1[now_] += sum[rs] - sum[last];
      rs = last;
      Pushup(now_);
    }
  }
  void Makeroot(int now_) {
    Access(now_);
    Splay(now_);
    Rev(now_);
  }
  int Find(int now_) {
    Access(now_);
    Splay(now_);
    while (ls) now_ = ls;
    Splay(now_);
    return now_;
  }
  void Split(int x_, int y_) {
    Makeroot(x_);
    Access(y_);
    Splay(y_);
  }
  void Link(int x_, int y_) {
    Makeroot(x_);
    // fa[x_] = y_;
    if (Find(y_) != x_) fa[x_] = y_;
  }
  void Cut(int x_, int y_) {
    // Split(x_, y_);
    // fa[x_] = son[y_][0] = 0;
    // Pushup(y_);
    Makeroot(x_);
    if (Find(y_) != x_ || fa[y_] != x_ || son[y_][0]) return ;
    fa[y_] = son[x_][1] = 0;
    Pushup(x_);
  }
  
  int query(int x_) {
    Makeroot(x_);
    return sum[x_];
  }

  void Init() {
    for (int i = 1; i <= nodenum; ++ i) {
      val[i] = sum[i] = node[i].val;
    }
    for (int i = 1; i <= nodenum; ++ i) {
      if (next[i]) Link(i, next[i]);
    }
  }
}
void Init() {
  n = read(), m = read(), q = read();
  
  nodenum = n;
  for (int i = 1; i <= n; ++ i) {
    node[i] = (Node) {i, i, 1, m + 1, i};
    st.insert(node[i]);
  }
  for (int i = 1; i <= q; ++ i) {
    int opt = read();
    if (opt == 1) {
      int a = read(), b = read();

      Node u1 = *st.lower_bound((Node) {0, a, 0, b, 0});
      Node u2 = *st.lower_bound((Node) {0, a + 1, 0, b, 0});
      node[++ nodenum] = (Node) {nodenum, a, b + 1, u1.r, u1.val};
      node[++ nodenum] = (Node) {nodenum, a + 1, b + 1, u2.r, u2.val};
      node[u1.id].r = node[u2.id].r = b;
      node[u1.id].val = node[u2.id].val = 0;

      st.erase(st.lower_bound(u1)), st.erase(st.lower_bound(u2));
      st.insert(node[u1.id]), st.insert(node[u2.id]);
      st.insert(node[nodenum - 1]), st.insert(node[nodenum]);
      /*
      struct Node {
        int id, a, l, r, val;
      */
      op[i] = (O) {1, a, b};
    } else {
      int a = read();
      op[i] = (O) {2, a, 0};
    }
  }
  for (std::set<Node>::iterator it = st.begin(); it != st.end(); ++ it) {
    std::set<Node>::iterator it1 = it;
    ++ it1;
    if (it1 == st.end()) break;
    if (it->a != it1->a) continue;
    next[it->id] = it1->id;
  }
  LCT::Init();
}
void modify(int x_, int y_) {
  int u1 = st.lower_bound((Node) {0, x_, 0, y_, 0})->id;
  int u2 = st.lower_bound((Node) {0, x_ + 1, 0, y_, 0})->id;

  LCT::Cut(u1, next[u1]), LCT::Cut(u2, next[u2]);
  std::swap(next[u1], next[u2]);
  LCT::Link(u1, next[u1]), LCT::Link(u2, next[u2]);
}
int query(int x_) {
  return LCT::query(st.lower_bound((Node) {0, x_, 0, 0, 0})->id);
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  Init();
  for (int i = 1; i <= q; ++ i) {
    if (op[i].opt == 2) {
      printf("%d\n", query(op[i].a));
    } else {
      modify(op[i].a, op[i].b);
    }
  }
  return 0;
}

D 倍增，DP

唉唉这不比 A 简单？

写在最后

学到了什么：

  • A：转化为经典数据结构问题；LCT 通过维护虚子树，维护可加性的子树信息。
  • B：双变量函数，但是两个变量有线性关系——则双变量函数对于单变量为单峰/单谷。

然后是日常的夹带私货环节：

<iframe allowfullscreen="allowfullscreen" frameborder="0" height="500" sandbox="allow-top-navigation allow-same-origin allow-forms allow-scripts" scrolling="no" src="//player.bilibili.com/player.html?isOutside=true&aid=113151819383297&bvid=BV14YthefEt1&cid=25895175154&p=1" width="100%"> </iframe>

标签：std,Contest,int,LL,Regional,Xian,kN,long,operatorname
From： https://www.cnblogs.com/luckyblock/p/18418794

相关文章

  • 2017 ACM/ICPC Asia Regional Qingdao Online(SDKD 2024 Summer Training Contest J2)
    C-TheDominatorofStrings题意给定n个串，问是否有一个串包含其他所有串，有就输出这个串。思路如果有解，答案必定是最长串，一一比较即可。(没想到.find()就能过......
  • he 2024 ICPC Asia East Continent Online Contest (I)
    A.WorldCup这道题目难点主要是读懂题意，然后按照题意手玩一下就出来了。#include<bits/stdc++.h>usingnamespacestd;usingi32=int32_t;usingi64=longlong;#defineinti64usingvi=vector<int>;voidsolve(){intn=32;via(n);for(a......
  • AtCoder Beginner Contest 371
    A-Jiro输入\(AB,BC,AC\)的大小关系，输出中位数。手动模拟一下。点击查看代码#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#defineullunsignedlonglongintread(){intx=0;boolf=false;charc=getchar();while(c<'......
  • The 17th Heilongjiang Provincial Collegiate Programming Contest A(思维 + 二分)
    题意有\(n\)本类型\(A\)的书题解点击查看代码#include<bits/stdc++.h>usingi64=longlong;voidsolve(){ inta,b,n,m,h; std::cin>>a>>b>>n>>m>>h; i64cnt=i64(n/b)*(h-a); if(cnt>=m-1)......
  • AtCoder Beginner Contest 371
    A-Jiro(abc371A)题目大意三个人，给定他们相互之间的大小关系。问谁在中间。解题思路排个序，大小结果就是题目给的，因为问的是中间是谁，所以写的时候并没在意是升序排还是降序排。神奇的代码#include<bits/stdc++.h>usingnamespacestd;usingLL=longlong;intmai......
  • AtCoder Beginner Contest 371
    ABC371总结AtCoderBeginnerContest371一些废话想着以后换一种方式写总结，不再以那种题解形式，写起来又累又难写，只对其中部分有意思的题目写出完整的题解。就是以随笔的形式，在打完比赛后写出自己的一些感悟，每道题做的过程中的一些思路、用时和需要改进的地方，就是类似随笔之类的......
  • AtCoder Beginner Contest 371
    https://atcoder.jp/contests/abc371C:暴力。思路是把1-8的点映射到全排列上面，然后把有的点去掉没的点加上取ans最小值。这题复杂度是\(8！\times7\times4\),暴力求全排列即可（第一次写暴力全排列思索了一会复杂度#include<bits/stdc++.h>usingnamespacestd;#definepiipai......
  • The 2024 CCPC Online Contest
    Preface最唐氏的一集，这场现场打的时候中间出现了“消失的150min”很难相信在93min过了D之后下一次过题要等到241min过E，虽然后面全力追赶最后也是出了9题，但罚时也是突破天际，险些拿下同题数罚时倒一后面分析了下最大的原因就是我比赛的时候想不出E导致心态崩了没法正......
  • The 2020 ICPC Asia Shenyang Regional Programming Contest
    D-JourneytoUn'Goro记\(p_i\)表示前缀\(i\)中\(\mathrmr\)的个数。则题目要求的是\(p_r-p_{l-1}\)为奇数最多有多少对。显然应该越平均越好。\(p_i\)总共有\(n+1\)个，则奇偶数的数量均不超过\(m=\left\lceil\frac{n+1}{2}\right\rceil\)，答案就是\((n+1-m)\time......
  • AtCoder Beginner Contest 370 补题记录
    A-RaiseBothHands题意：给出Snuke举的左右手情况，如果只举左手，输出Yes，如果只举右手，输出No，否则输出Invalid思路：举左手：（l==1&&r==0)举右手：(l==1&&r==0)其他情况都是Invalidvoidsolve(){intl=read(),r=read();if(l==1&&r==0){......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99