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$。

注意：

只有红色能改变奇偶性
要求字典序最小，那先考虑放$b$。
为什么要记录$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();

}