首页 > 其他分享 >The 2021 ICPC Asia Macau Regional Contest

The 2021 ICPC Asia Macau Regional Contest

时间：2023-09-14 17:44:11浏览次数：32  
标签：cnt return Macau Contest int Regional ++ ans sa

目录

写在前面

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

当了一场口胡选手。

我是彩笔。

以下按个人向难度排序。

A

随便找条路径，检查路径是否满足条件，满足则直接输出，否则倒序输出。

Code by YRMrSu：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 1e6+6;
LL n,a[100][100],ans[N],cnt;
void work(){
	cnt=0;
	cin>>n;
	for(LL i=1;i<=n;i++){
		for(LL j=1;j<=n;j++){
			cin>>a[i][j];
		}
	}
	if(n==1){
		cout<<"1\n";
		return;
	}
	LL up=0,dn=0;
	for(LL i=1;i<=n;i++){
		if(i!=1){
			if(a[i][1]>a[i-1][1])up++;
			else dn++;
		}
		for(LL j=1;j<n;j++){
			ans[++cnt]=a[i][j];
			if(a[i][j+1]>a[i][j])up++;
			else dn++;
		}
		ans[++cnt]=a[i][n];
		i++;
		if(i>n)break;
		if(a[i][n]>a[i-1][n])up++;
		else dn++;
		for(LL k=n;k>1;k--){
			ans[++cnt]=a[i][k];
			if(a[i][k-1]>a[i][k])up++;
			else dn++;
		}
		ans[++cnt]=a[i][1];
	}
	if(up>dn){
		for(LL i=cnt;i>1;i--){
			cout<<ans[i]<<' ';
		}
		cout<<ans[1]<<'\n';
	}
	else{
		for(LL i=1;i<cnt;i++){
			cout<<ans[i]<<' ';
		}
		cout<<ans[cnt]<<'\n';
	}
}
int main(){
	ios::sync_with_stdio(false);
	LL _=1;
	cin>>_;
	while(_--){
		work();
	}
}

K

根据二进制的贪心性质，按顺序把边加入图中取第一个构成的环即可。

正确性显然，如果加入这条边后能构成两个环，则再加边之前已经成环。

Code by nebulyu：

#include<bits/stdc++.h>
#define pb emplace_back
#define ffor(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int N=1e5+5;
int n,m;
int f[N];int g(int p){return (p^f[p]?f[p]=g(f[p]):p);}
vector<int>ov[N];int sum[N];
int sta[N];
int ans[N],len;
int tg=0;
int S,T;
void dfs(int p,int dep,int f){
	if(tg)return ;
	if(p==T){
		tg=1;
		ffor(i,1,dep)ans[i]=sta[i];
		len=dep;
		return ;
	}
	for(auto e:ov[p]){int x=sum[e]-p;
		if(x==f)continue;
		sta[dep+1]=e,dfs(x,dep+1,p);
	}
}
void solve(){
	cin>>n>>m;
	ffor(i,1,n)f[i]=i,ov[i].clear();
	tg=0,len=0;
	ffor(i,1,m){
		int p1,p2;cin>>p1>>p2;
		if(tg)continue;
		if(g(p1)!=g(p2))f[g(p1)]=g(p2),ov[p1].pb(i),ov[p2].pb(i),sum[i]=p1+p2;
		else{
			S=p1,T=p2;
			dfs(S,0,0);
			ans[++len]=i;
			sort(ans+1,ans+1+len);
			ffor(j,1,len)cout<<ans[j]<<" \n"[j==len];
		}
	}
	if(!tg)cout<<-1<<"\n";
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T;cin>>T;while(T--)solve();
	return 0;
}

F

发现对一个节点进行操作等价于令这个点权值 \(-n\)，再令全部点权值 \(+1\)。

猜个结论，如果有终结态则操作次数至多为 \(n-1\) 次，操作 \(n-1\) 次之后相当于所有节点都加上了 \(n-1\)，因此所有被减去了 \(n-1\) 的节点又可以继续被操作，然后根据上面的等价用优先队列大力模拟即可。

赛时猜的操作数上界是 \(n-2\)，不过也过了哈哈，也懒得深究了、、、

Code by nebulyu：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define pb emplace_back
#define ffor(i,a,b) for(ll i=a;i<=b;++i)
using namespace std;
using ll=long long;
const ll N=5e5+5;
using pii=pair<ll,ll>;
ll n;
priority_queue<pii>pq;
ll ans[N];
void solve(){
	cin>>n;
	ffor(i,1,n){
		ll x;cin>>x;pq.push(pii(x,i));
	}
	ll tim=0,cnt=0;
	while(tim<=n-2){
		pii x=pq.top();
		if(x.first+cnt<=n-2){
			while(pq.size()){
				pii x=pq.top();pq.pop();
				ans[x.second]=x.first+cnt;
			}
			ffor(i,1,n){
				cout<<ans[i];if(i^n)cout<<" ";
			}
			return ;
		}
		pq.pop();
		++cnt,x.first-=n;
		pq.push(x);
		++tim;
	}
	cout<<"Recurrent";
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	solve();
	return 0;
}

C

可以保留的点合法当且仅当它们的极角范围 \(\le \pi\)，于是极角排序后直接双指针枚举点数最大的合法区间即可。

然而赛时没想到这么简单。赛时做法是考虑过某个点和原点构成的一条直线，将直线某一侧的点全部删除即为合法方案，求删除点数的最小值即可。

Code by nebulyu：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define pb emplace_back
#define ffor(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
using ll=long long;
const int N=2e6+5;
int get_lv(ll x,ll y){
	if(x>0&&y==0) return 1;
	if(x>0&&y>0) return 2;
	if(x==0&&y>0) return 3;
	if(x<0&&y>0) return 4;
	if(x<0&&y==0) return 5;
	if(x<0&&y<0) return 6;
	if(x==0&&y<0) return 7;
	if(x>0&&y<0) return 8;
	return 9;
}
struct node{
	ll x,y,cnt;
	bool operator < (node p){
		if(get_lv(x,y)^get_lv(p.x,p.y)) return get_lv(x,y)<get_lv(p.x,p.y);
		return x*p.y-y*p.x>0;
	}
	bool operator == (node p){
		if(get_lv(x,y)^get_lv(p.x,p.y))return 0;
		return x*p.y-y*p.x==0;
	}
	void print(){
		cerr<<x<<" "<<y<<" "<<cnt<<"\n"; 
	}
}tmp[N],ar[N];
bool checkpos(node p1,node p2){
	return p1.x*p2.y-p2.x*p1.y>=0;
}
bool checkzr(node p1,node p2){
	return p1.x*p2.y-p2.x*p1.y==0;
}
int n,m;
ll pre[N];
void solve(){
	cin>>m;
	ffor(i,1,m)cin>>tmp[i].x>>tmp[i].y;
	sort(tmp+1,tmp+1+m);
	ar[n=1]=tmp[1],ar[1].cnt=1;
	ffor(i,2,m)if(tmp[i]==tmp[i-1])++ar[n].cnt;
	else ar[++n]=tmp[i],ar[n].cnt=1;
	ffor(i,1,n)ar[i+n]=ar[i];
	ffor(i,1,n+n)pre[i]=pre[i-1]+ar[i].cnt;
	ll p=1,ans=m;
	ffor(i,1,n){
		while(p<i+n-1&&checkpos(ar[p],ar[p+1])&&checkpos(ar[i],ar[p+1]))++p;
		if(p<i)p=i;
		ll lv=pre[p]-pre[i],rv=m-lv-ar[i].cnt;
		ans=min({ans,lv,rv});
//		cerr<<i<<" "<<p<<"\n";
//		cerr<<lv<<" "<<mv<<" "<<rv<<"\n";
	}
	cout<<ans<<"\n";
//	ffor(i,1,n)ar[i].print();
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T;cin>>T;while(T--)solve();
	return 0;
}

G

显然在操作过程中数列最多只有 \(n\) 种形态。

显然若要将某个还未被扫描过且不在扫描区域 \([1, k]\) 内的数 \(i\) 移动到扫描区域内，并且操作数最小的方案只有两种，即将 \(i\) 移动到位置 1 或 \(k\)。基于这个结论考虑一个 DP，设 \(f_{i, 0 / 1}\) 表示已经扫描过 \(1\sim i\)，此时数列的形态是 \(i\) 在位置 1 / \(i\) 在位置 \(k\) 时所需的最小步数。

发现对于某种数列的形态，我们可以很方便地求出把某个数移动到位置 1 或 \(k\) 所需的步数，并且移动后数列的形态也是唯一的。于是考虑再维护 \(g_{i, 0/1}\) 表示数列的形态为 \(i\) 在位置 1/ \(i\) 在位置 \(k\) 时，\([1, k]\) 内最小的没有出现过的大于 \(i\) 的数，此时对于 \(g_{i, 0/1} \le n\) 的情况我们就可以完成如下转移：

\[\begin{aligned} f_{i, 0} \rightarrow f_{g_{i, 0}, 0/1}\\ f_{i, 1} \rightarrow f_{g_{i, 1}, 0/1} \end{aligned}\]

\(g\) 可以通过在原数列上构建滑动窗口的权值线段树，在权值线段树上二分求区间内最小的没有出现过的数来预处理，为了方便实现时把原数组复制了一份扔在了后面；预处理出初始状态时 \([1, k]\) 中的 \(\text{mex}\) 并求得 \(f_{\operatorname{mex}, 0/1}\) 后即可进行转移。

当 \(g_{i, 0/1} > n\) 时表示将 \(i\) 移项位置 1/\(k\) 后即可完成所有数的扫描，即有：

\[\text{answer} = \min \{ f_{i, j} | g_{i, j} > n\} \]

总时间复杂度\(O(n\log n)\) 级别，瓶颈在于预处理 \(g\)。似乎可以在权值树状数组上二分预处理 \(g\) 来进一步缩小常数，但是我不会呃呃，留坑！

一开始没想到 \(g\) 还可以预处理于是脑瘫地对 \(2\times n\) 的原序列建了主席树转移时在线查呃呃呃呃，T 爆了，改成预处理之后 1A 了，好想死。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e6 + 10;
const LL kInf = 1e18 + 2077;
//=============================================================
int n, k, a[kN << 1], pos[kN];
int g[kN][2];
LL ans, f[kN][2];
//=============================================================
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 Seg {
  #define ls (now_<<1)
  #define rs (now_<<1|1)
  #define mid ((L_+R_)>>1)
  const int kNode = kN << 2;
  int sum[kNode];
  void Pushup(int now_) {
    sum[now_] = sum[ls] + sum[rs];
  }
  void Modify(int now_, int L_, int R_, int pos_, int val_) {
    if (L_ == R_) {
      sum[now_] += val_;
      return ;
    }
    if (pos_ <= mid) Modify(ls, L_, mid, pos_, val_);
    else Modify(rs, mid + 1, R_, pos_, val_); 
    Pushup(now_);
  }
  int Query(int now_, int L_, int R_, int minval_) {
    if (minval_ <= L_) {
      if (R_ - L_ + 1 == sum[now_]) return n + 1;
      
      if (L_ == R_) return L_;
      if (sum[ls] < mid - L_ + 1) return Query(ls, L_, mid, minval_);
      return Query(rs, mid + 1, R_, minval_);
    } else {
      int ret = n + 1;
      if (R_ < minval_) return n + 1;
      if (minval_ < mid) ret = Query(ls, L_, mid, minval_);
      if (ret == n + 1) ret = Query(rs, mid + 1, R_, minval_);
      return ret;
    }
  }
  #undef ls
  #undef rs
  #undef mid
}
void Init() {
  n = read(), k = read();
  for (int i = 1; i <= n; ++ i) a[i] = a[i + n] = read(), pos[a[i]] = i;
  for (int i = 1; i <= k; ++ i) Seg::Modify(1, 1, n, a[i], 1);
  for (int i = 1; i <= n; ++ i) {
    g[a[i]][0] = Seg::Query(1, 1, n, a[i]);
    g[a[i + k - 1]][1] = Seg::Query(1, 1, n, a[i + k - 1]);
    Seg::Modify(1, 1, n, a[i], -1);
    Seg::Modify(1, 1, n, a[i + k], 1);
  }
  for (int i = 1; i <= k; ++ i) Seg::Modify(1, 1, n, a[i], -1);
}
LL Solve() {
  int mex = 1;
  for (int i = 1; i <= n; ++ i) f[i][0] = f[i][1] = kInf;
  for (int i = 1; i <= k; ++ i) {
    if (pos[i] <= k) ++ mex;
    else break;
  }
  if (mex == n + 1) return 0;

  ans = kInf;
  f[mex][0] = std::min(pos[mex] - 1, n + 1 - pos[mex]);
  f[mex][1] = std::min(pos[mex] - k, n + k - pos[mex]);
  for (int i = mex; i <= n; ++ i) {
    if (f[i][0] == kInf) continue;
    int w0 = g[i][0];
    if (w0 > n) ans = std::min(ans, f[i][0]);
    else {
      int piw0 = pos[w0] - (pos[i] - 1);
      if (piw0 <= 0) piw0 += n;

      f[w0][0] = std::min(f[w0][0], f[i][0] + std::min(piw0 - 1, n + 1 - piw0));
      f[w0][1] = std::min(f[w0][1], f[i][0] + std::min(piw0 - k, n + k - piw0));
    }

    int w1 = g[i][1];
    if (w1 > n) ans = std::min(ans, f[i][1]);
    else {
      int piw1 = pos[w1] - (pos[i] - k);
      if (piw1 <= 0) piw1 += n;
      if (piw1 > n) piw1 -= n;

      f[w1][0] = std::min(f[w1][0], f[i][1] + std::min(piw1 - 1, n + 1 - piw1));
      f[w1][1] = std::min(f[w1][1], f[i][1] + std::min(piw1 - k, n + k - piw1));
    }
  }
  return ans;
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  int T = read();
  while (T --) {
    Init();
    printf("%lld\n", Solve());
  }
  return 0;
}

I

SA 经典套路，考虑把所有节点对应的字符串加不可匹配字符连起来，记录每个位置对应哪个节点后跑 SA。然后枚举后缀数组，将后缀数组中相邻的两个位置对应的节点之间连一条长度为 height 的边，在这个图上跑 Kruscal 求最大生成树即可。

正确性显然，对于某个节点，这样搞可以保证该节点至少与和它的 LCS 最大的节点之间连了一条无向边，并且可以保证图肯定是连通的。

注意不可匹配字符也需要两两不相等，所以字符集也是 \(O(n)\) 级别的，注意写法。赛时没注意一直 WA，我是战犯，好想死。

时间复杂度 \(O(|s_i|\log |s_i|)\) 级别，但是因为倍增求 SA 太呃呃了被卡了，抄了个 SA-IS 板子跑了 1.6s。

题解的写法是广义 SAM 维护每个节点上的字符串集合再考虑按深度合并，但是这东西太 SA 套路了、、、之后想补再补了。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 4e6 + 10;
//=============================================================
int nodenum, n, m, from[kN];

int a[kN];
char s[kN];

int fa[kN];
struct Edge {
  int u, v, w;
} e[kN << 1];
//=============================================================
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;
}
struct SA {
    inline bool isLMS(bool *tp, int x) {
        return (x && tp[x] && !tp[x - 1]);
    }
    inline void idsort(int *S, int *sa, bool *tp, int *buk, int *lbk, int *sbk, int n, int m) {
        for (register int i = 0; i <= n; ++i)
            if (sa[i] > 0 && !tp[sa[i] - 1])
                sa[lbk[S[sa[i] - 1]]++] = sa[i] - 1;

        for (register int i = 1; i <= m; ++i)
            sbk[i] = buk[i] - 1;

        for (register int i = n; i >= 0; --i)
            if (sa[i] > 0 && tp[sa[i] - 1])
                sa[sbk[S[sa[i] - 1]]--] = sa[i] - 1;
    }
    inline bool equal(int *S, bool *tp, int x, int y) {
        do {
            if (S[x] != S[y])
                return 0;

            ++x, ++y;
        } while (!isLMS(tp, x) && !isLMS(tp, y));

        return S[x] == S[y];
    }
    inline int *sais(int *S, int n, int m) {
        bool *tp = new bool[n + 5];
        int *pos = new  int[n + 5];
        int *rak = new  int[n + 5];
        int *sa = new  int[n + 5];
        int *buk = new  int[m + 5];
        int *lbk = new  int[m + 5];
        int *sbk = new  int[m + 5];

        for (register int i = 0; i <= m + 2; ++i)
            buk[i] = 0;

        for (register int i = 0; i <= n + 2; ++i)
            sa[i] = rak[i] = -1;

        lbk[0] = sbk[0] = 0;

        for (register int i = 0; i <= n; ++i)
            ++buk[S[i]];

        for (register int i = 1; i <= m; ++i) {
            buk[i] += buk[i - 1],
                      lbk[i] = buk[i - 1],
                               sbk[i] = buk[i] - 1;
        }

        tp[n] = 1;

        for (register int i = n - 1; i >= 0; --i) {
            if (S[i] < S[i + 1])
                tp[i] = 1;
            else if (S[i] > S[i + 1])
                tp[i] = 0;
            else
                tp[i] = tp[i + 1];
        }

        int cnt = 0;

        for (register int i = 1; i <= n; ++i)
            if (tp[i] && !tp[i - 1])
                pos[cnt++] = i;

        for (register int i = 0; i < cnt; ++i)
            sa[sbk[S[pos[i]]]--] = pos[i];

        idsort(S, sa, tp, buk, lbk, sbk, n, m);
        int las = -1, tot = 1;
        bool rep = 0;

        for (register int i = 1; i <= n; ++i) {
            int x = sa[i];

            if (!isLMS(tp, x))
                continue;

            if (las >= 0 && !equal(S, tp, x, las))
                ++tot;

            if (las >= 0 && tot == rak[las])
                rep = 1;

            rak[x] = tot, las = x;
        }

        rak[n] = 0;
        int ps = 0;
        int *sa1, *s1 = new int[cnt + 5];

        for (register int i = 0; i <= n; ++i)
            if (rak[i] >= 0)
                s1[ps++] = rak[i];

        if (!rep) {
            sa1 = new int[cnt + 5];

            for (register int i = 0; i < cnt; ++i)
                sa1[s1[i]] = i;
        } else
            sa1 = sais(s1, cnt - 1, tot);

        lbk[0] = sbk[0] = 0;

        for (register int i = 1; i <= m; ++i) {
            lbk[i] = buk[i - 1],
                     sbk[i] = buk[i] - 1;
        }

        for (register int i = 0; i <= n + 2; ++i)
            sa[i] = -1;

        for (register int i = cnt - 1; i >= 0; --i)
            sa[sbk[S[pos[sa1[i]]]]--] = pos[sa1[i]];

        idsort(S, sa, tp, buk, lbk, sbk, n, m);

        delete (tp), delete (buk), delete (sbk), delete (lbk), delete (s1), delete (sa1);
        return sa;
    }
    int sa[kN], rk[kN], ht[kN];
    inline void build(int *a, int n, int m) {
        int *p = sais(a, n, m);

        for (register int i = 0; i <= n; ++i)
            sa[i] = p[i];

        for (register int i = 0; i <= n; ++i)
            rk[p[i]] = i;

        for (register int i = 0, j = 0; i <= n; ++i)
            if (rk[i]) {
                if (j)
                    --j;

                while (a[i + j] == a[j + p[rk[i] - 1]])
                    ++j;

                ht[rk[i]] = j;
            }
    }
    inline int &operator [](const int &i) {
        return sa[i];
    }
} sa;
bool cmpedge(Edge fir_, Edge sec_) {
  return fir_.w > sec_.w;
}
int Find(int x_) {
  return fa[x_] == x_ ? x_ : fa[x_] = Find(fa[x_]);
}
void Merge(int x_, int y_) {
  int fax = Find(x_), fay = Find(y_);
  if (fax == fay) return ;
  fa[fax] = fay;
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  nodenum = read();
  
  m = 200;
  for (int i = 1; i <= nodenum; ++ i) {
    scanf("%s", s + 1);
    int delta = strlen(s + 1);
    for (int j = 1; j <= delta; ++ j) a[++ n] = s[j], from[n] = i;
    if (i < nodenum) a[++ n] = ++ m;
  }
  // printf("%s", s + 1);
  a[n + 1] = 1;
  sa.build(a + 1, n, m + 1);
  for (int i = 1; i <= n; ++ i) sa[i] ++;

  m = 0;
  for (int i = 2; i <= n; ++ i) {
    e[++ m] = (Edge) {from[sa[i - 1]], from[sa[i]], sa.ht[i]};
  }
  std::sort(e + 1, e + m + 1, cmpedge);
  
  LL ans = 0;
  for (int i = 1; i <= nodenum; ++ i) fa[i] = i;
  for (int i = 1; i <= m; ++ i) {
    int u_ = e[i].u, v_ = e[i].v, w_ = e[i].w;
    if (Find(u_) == Find(v_)) continue;
    Merge(u_, v_);
    ans += w_;
  }
  printf("%lld\n", ans);
  return 0;
}

写在最后

学到了什么：

  • SA 求多串两两最长公共子串时字符串之间的不可匹配字符要两两不同。
  • 注意字符集大小。
  • 预处理是好的、、、

标签：cnt,return,Macau,Contest,int,Regional,++,ans,sa
From： https://www.cnblogs.com/luckyblock/p/17703018.html

相关文章

  • AtCoder Beginner Contest 319 全部题解
    AtCoderBeginnerContest319全部题解ALegendaryPlayers该题只需使用判断来写出所有的答案，注意不要复制错。#include<bits/stdc++.h>usingnamespacestd;strings;intmain(){ cin>>s; if(s=="tourist")cout<<3858<<endl; if(s=="ksun4......
  • The 2020 ICPC Asia Shenyang Regional Programming Contest DFIK
    The2020ICPCAsiaShenyangRegionalProgrammingContest-CodeforcesDFIKD.JourneytoUn'Goro思路：思维+搜索一开始以为是构造，好吧但是是搜索。我们先考虑什么时候是最大值？首先考虑，题目要求我们从\(i->j\)且红色的数量是奇数被认为是好的。那么我们考虑记录\(p......
  • 2022-2023 ACM-ICPC German Collegiate Programming Contest (GCPC 2022)
    A.AlternativeArchitecture当倾斜放置时，一定可以构成直角三角形。枚举高用勾股定理算出底，然后在利用相似三角形即可算出另一条构成的直角三角形的边长，此时判断边是否都是整数即可。原图实际上点在格子上，一个常见的套路是边减一就可以转换成点在定点上。#include<bits/stdc+......
  • AtCoder Beginner Contest 044 C (背包DP、思维、*1583)
    C-TakandCards题意：给定$N$个正整数$x_1,x_2,\cdot\cdot\cdot,x_n$和一个正整数$A$,问从中选择$k$个数\((k>0)\),满足：这$k$个数的平均值是$A$的方案总数是多少?思路：......
  • Codeforces Round 819 (Div. 1 + Div. 2) and Grimoire of Code Annual Contest 2022
    给一个长为\(n\)的正整数数组，执行以下操作严格一次。选择\(l,r,(1\leql<r\leqn)\)，任意一个正整数\(k\)。重复\(k\)次：让\([l,r]\)的数组成环，按顺时针走一次。希望\(a_n-a_1\)最大，找到这个数。分类讨论题。先判断\(n\)为\(1\)时\(a_n-a_1\)......
  • 2019-2020 ACM-ICPC Brazil Subregional Programming Contest
    D.DenouncingMafia给定一颗树，然后给定\(k\)个起点，对于每个起点来说，从该点到根节点的一条链都会被染色，求最多有几个点会被染色\(3\leqn\leq1e5,1\leqk\leqn\)题解我们贪心的来看，起点一定会选择在叶子节点，假设叶子节点的数量为\(cnt\)，所以如果\(k\geqcnt\)，那么......
  • 2022 Hubei Provincial Collegiate Programming Contest G. Brick（gym103729）
    大意给出底层高度，用1*2的砖块将总形状铺成等高矩形，使得高度最小（不能放在外面）题解奇妙做法当高度同奇偶时显然x可以的话x+2也可以，直接加一层竖的，所以首先分奇偶二分高度有解的必要条件1是，把矩形黑白方格染色之后未填的黑=白（一个1*2刚好覆盖1黑1白）然后从左往右放砖块，可以感受......
  • 2019 ICPC Universidad Nacional de Colombia Programming Contest
    A.Amazon给定\(n\)条直线（存在共线的情况），在每两条垂直的直线的交点处需要建一个交叉点，求交叉点的数量，注意需要去除共线时候的交叉点题解因为要除去共线的情况，我们考虑将一条直线以方向向量\(v\)，与\(x\)轴的交点的横坐标\(x\)的方式存储注意：对于\(v\)来说需要最简形......
  • 【题解】AtCoder Regular Contest 161
    评价：感觉这场题目质量不咋地啊，都是一些乱搞题A.MakeM题目描述：\(N\)是一个正奇数。我们称一个长度为\(N\)的序列\(S\)是M型序列，当前仅当对于所有的\(i=2,4,6,\dots,N-1\)（即偶数位），都有\(S_{i-1}<S_{i}\)且\(S_{i}>S_{i+1}\)。现在给定你一个长度为\(N\)的序列\(A......
  • 【题解】AtCoder Regular Contest 162
    A.EkidenRace题目描述：有\(n\)个人参加了往返赛跑，每个人有一个编号\(1\)到\(n\)。已知以下信息：如果按照往路的成绩排序，那么任何两个人的成绩都不相同。同时第\(i\)个人在往路中排名第\(i\)。如果按照往返的成绩排序，那么任何两个人的成绩都不相同。同时第\(i\)个人......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99