首页 > 其他分享 >The 2020 ICPC Asia Shenyang Regional Programming Contest DFIK

The 2020 ICPC Asia Shenyang Regional Programming Contest DFIK

时间:2023-09-12 11:34:51浏览次数:46  
标签:begin end Contest int DFIK Regional times HM vx

The 2020 ICPC Asia Shenyang Regional Programming Contest - Codeforces DFIK

D. Journey to Un'Goro

思路:思维+搜索

一开始以为是构造,好吧但是是搜索。

我们先考虑什么时候是最大值?

首先考虑,题目要求我们从\(i->j\)且红色的数量是奇数被认为是好的。那么我们考虑记录\(pre[i]\)表示前\(i\)个里面红色的数量。那么从\(i->j\)的红色的数量就可以表示为:\(pre[j]-pre[i-1]\)。又因为要求红色的数量是奇数,那么对于从\(i->j\)红色的数量是奇数那么:\(pre[j]\)和\(pre[i-1]\)的奇偶性应该不一样。那么我们考虑对于\([1,n]\)里面\(pre[i]\)有\(x\)个奇数和\(y\)个是偶数,那么最终的答案对数就是\(xy\)。那么如果要求最大的,两个数的和为\(n\)且乘积的值最大,肯定是两个越接近的数的乘积。那么答案就是\(\lfloor \dfrac{n+1}{2} \rfloor\times \lceil\dfrac{n+1}{2} \rceil\)。

接下来输出方案数。原本以为答案只输出前\(100\)种只是为了不要输出太多,其实是为了方便我们剪枝。之后我们只要考虑去搜就\(ok\)啦。

剪枝的话:记录前\(i\)步,前缀是偶数出现次数\(cnt_0\),前缀是奇数出现次数\(cnt_1\),当前\(pre[i]\)的奇偶性\(st\),\(0\)表示偶数,\(1\)表示奇数。如果当\(cnt_0\)或者\(cnt_1\)其中一个大于一半以上就直接\(return\)了,因为肯定不满足。如果方案数已经有\(100\)了,那么也直接\(exit\)。

注意:

  1. 只有红色能改变奇偶性
  2. 要求字典序最小,那先考虑放\(b\)。
  3. 为什么要记录\(st\)?因为如果当前是奇数那么加上一个\(b\)还是奇数,否则如果是偶数加上一个数还是偶数,我需要知道前缀\(r\)是奇数还是偶数来确定当前加的这个使得奇数前缀增加还是偶数前缀增加。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll n,hav;
char a[N];
void dfs(int step,int cnt0,int cnt1,int st)
{
    if(hav>=100)exit(0);
    if(cnt0>(ll)ceil(1.0*(n+1)/2)||cnt1>(ll)ceil(1.0*(n+1)/2))return;
    if(step>n)
    {
        for(int i = 1;i <= n; i++)
            cout<<a[i];
        cout<<"\n";
        hav++;
        return;
    }
    a[step] = 'b';
    dfs(step+1, cnt0 + (st^1), cnt1 + st, st);
    
    a[step] = 'r';
    st ^= 1;
    dfs(step+1, cnt0 + (st^1), cnt1 + st, st);
}

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    cin>>n;
    cout<<(n+1)/2*(ll)ceil((n+1)*1.0/2)<<"\n";
    dfs(1,1,0,0);
    return 0;
}

F. Kobolds and Catacombs

思路:思维

我们先对原数组\(a\)排序得到最终数组\(b\)。我们去求这两个数组的前缀和,当且仅当前缀和一样的时候可以被分成一段,那么我们只需要判断有几个前缀和一样就可以了。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e6 + 10;
ll a[N],b[N],sa[N],sb[N];
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int n;
    cin>>n;
    for(int i = 1;i <= n; i++)
        cin>>a[i],b[i] = a[i];
    sort(b+1,b+1+n);
    for(int i = 1;i <= n; i++)
        sa[i] = sa[i-1]+a[i],sb[i] = sb[i-1]+b[i];
    int cnt = 0;
    for(int i = 1;i <= n; i++)
        if(sa[i]==sb[i])cnt++;
    cout<<cnt<<"\n";
    return 0;
}

I. Rise of Shadows

思路:数论,追击问题,我们以时针作为参照物(静止不动),相对运动速度针对分针分析。

\(v_h绝对 = \dfrac{2\pi}{HM},v_m绝对= \dfrac{2\pi}{M}\)

\(v_m相对 = v_m绝对-v_h绝对 = \dfrac{2\pi}{M}-\dfrac{2\pi}{HM} = (H-1)\dfrac{2\pi}{M} = (H-1)v_h绝对\)

相当于分针相对于时针以每分钟\((H-1)\)的速度运动。

\(t\times (H-1)v_h绝对 \bmod HM \le \alpha = A\times v_h绝对\)

其中\(t\in[0,HM)\)

那么柿子转化为:\(t\times (H-1)v_h绝对 \bmod HM \le |\alpha| = |A\times v_h绝对|\)

即:\(t\times (H-1) \bmod HM \le |A|\)

根据剩余定理\(3\):如果\(a_1,a_2...a_m\)是模\(m\)的一个完全剩余系,且有\((k,m) = 1\),那么\(ka_1,ka_2...ka_m\)也是模\(m\)的一个完全剩余系。更一般地,\(ka_i+l\)也是完全剩余系。

\(g = \gcd(H-1,HM)\)

为满足互质条件,同除\(g\),那么\(t\times (H-1)/g \bmod HM/g \le |A/g|\)

那么:$ -A/g \le t\times (H-1)/g \bmod HM/g \le A/g$

同时\(t\in[0,HM/g)\)

接下来只需求解出\(t\)的整数解的个数。

因为\(t\)是\(\mod HM/g\)的完全剩余系,又\(((H-1)/g,HM/g)=1\),那么\(t(H-1)/g\)也是构成模\(HM/g\)意义下的完全剩余系。

由于$\bmod \(之后余数\)\le A/g$,因此一共又\(1,2,3,...,A/g\),一共\(A/g\)个,并且无重复。即\(t\)于余数值一一对应。在\(t\in[0,HM/g)\)中一共有\(2*(A/g)+1\)个。

再把\(t\)还原到\(t\in[0,HM]\),答案就是\(g*(2*(A/g)+1)\)个。

注意特判:\(A=\dfrac{HM}{2}\),此时\(\alpha=\pi,t\in[0,HM)\)所有都满足,答案是\(HM\)。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll H,M,A;
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    cin>>H>>M>>A;
    if(2*A==H*M)cout<<H*M<<"\n";
    else
    {
        //(H-1)t mod HM = |A|
        ll g = __gcd(H-1,H*M);
        cout<<(2*(A/g)+1)*g<<"\n";
    }
    return 0;
}

K.Scholomance Academy

思路:小模拟

注意:分界点的处理。考虑,如果去除分界点会怎么样呢?会变成一条斜线,我们考虑把它拉平(emmm,可能有点抽象hh)。

#include<bits/stdc++.h>

using namespace std;


typedef long long ll;

const int N = 1e6 + 10;

vector<int> vx;
vector<int> a, b;
vector<pair<double, double>> event;
int n;
void solve()
{
	cin>>n;
	for(int i = 1; i <= n; i++)
	{
		char opt[2];	int x;	
		// cin>>opt>>x;
		scanf("%s%d", opt, &x);
		vx.push_back(x);
		vx.push_back(x - 1);
		vx.push_back(x + 1);
		// mp[x]++;
		if(opt[0] == '+')
			a.push_back(x);
		else
			b.push_back(x);
	}
	sort(vx.begin(), vx.end());
	vx.erase(unique(vx.begin(), vx.end()), vx.end());
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	int sza = a.size(), szb = b.size();
	for(auto x : vx)
	{
		// if(mp[x] >= 2)	continue;
		int TP = 0, FN = 0, FP = 0, TN = 0;
		if(lower_bound(a.begin(), a.end(), x) == a.end())
			TP = 0, FN = sza;
		else
		{
			int sz = lower_bound(a.begin(), a.end(), x) - a.begin() + 1;
			TP = sza - sz + 1;
			FN = sza - TP;
		}
		if(lower_bound(b.begin(), b.end(), x) == b.end())
			TN = szb;
		else	
		{
			int sz = lower_bound(b.begin(), b.end(), x) - b.begin() + 1;
			FP = szb - sz + 1;
			TN = szb - FP;
		}
		double TPR = 1.0 * TP / (1.0 * TP + FN);
		double FPR = 1.0 * FP / (1.0 * TN + FP);
		// cout<<"x : "<<x<<"  FPR : "<<FPR<<"  TPR : "<<TPR<<'\n'; 
		// if(FPR == 0.5 && TPR == 0.5)	continue;

		event.push_back({FPR, TPR});
	}
	event.push_back({0.0, 0.0});
	sort(event.begin(), event.end());
	int m = event.size();
	double res = 0;
	for(int i = 1; i < m; i++)
	{
		double tx = event[i - 1].first, ty = event[i - 1].second;
		double x = event[i].first, y = event[i].second;
		
		if(x == 0.5 && y == 0.5)
			y = 0.25;
		// cout<<"x : "<<x<<"  y : "<<y<<'\n';
		if(x != tx && y != ty)
				y = ty;

		res = res + (x - tx) * y;
	}
	// cout<<res<<'\n';
	printf("%.11lf\n", res);

}
int main()
{
	// ios::sync_with_stdio(false);
	// cin.tie(nullptr);	cout.tie(nullptr);

	solve();

}

标签:begin,end,Contest,int,DFIK,Regional,times,HM,vx
From: https://www.cnblogs.com/nannandbk/p/17695740.html

相关文章

  • 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\)个人......
  • AtCoder Grand Contest 041 F Histogram Rooks
    洛谷传送门AtCoder传送门神题!!!!!!!!!/bx全部格子都被覆盖不好处理,考虑钦定\(k\)个格子不被覆盖,容斥系数就是\((-1)^k\)。发现网格的行不一定连续,但是列是连续的。如果一列有格子被钦定,那么这一列就不能放棋子。由此想到枚举不能放棋子的列(至少有一个棋子被钦定的列)集合\(S\),把......
  • AtCoder Beginner Contest 318 - D(状压 dp)
    目录D-GeneralWeightedMaxMatchingD-GeneralWeightedMaxMatching题意给定无向图,边有边权。让你选择一组边,满足任意两边不相交且总边权和最大。顶点数$\le16$思路状压DP求解该问题状态:利用n位二进制表示每个顶点是否已经被选择,0表示该顶点未选,1表示当前......