【Codeforces】Educational Codeforces Round 156 [Rated for Div. 2]

hh本蒟蒻第一次记录cf。

复盘

ab题目比较清晰，只开了这两题，后面看了下cd，即使开了翻译也看不懂题目是什么意思，最后放弃睡觉了。。

a是一道思维题，翻了下别人写的发现大家写的各不相同hh

b是一道数学题，过程有点繁琐，需要细心。

Problem - A - Codeforces

数学巧思

题意：

仍然是t组测试哈，给定一个数n，问是否有a+b+c=n，a%3，b%3，c%3不为0，如果存在输出yes并输出这三个数，否则输出no。

设a=3k1+d1，b=3k2+d2，c=3k3+d3

显然，d1，d2，d3只能是1或2

那么我们就只需要对余数进行讨论就行了，

比如给定1和2，这两个数当然是满足条件的，只需要（n-3）%3不为0就好了，也就是（n-3）=3*k+1或2（k>=1）

这一个条件不足以涵盖所有情况，也就是只要还需要n-(3*k+1)，n-(3*k+2)，即覆盖余数为0,1,2这三种情况

#include
signed main()
{
	int t;
	std::cin>>t;
	while(t--)
	{
		int x;
		std::cin>>x;
		if((x-3)%3&&(x-3)!=1&&(x-3)!=2&&(x-3)>0)
		{
			std::cout<<"YES"<<'\n'<<"1 2 "<-3<<'\n';
			continue;
		}
		if((x-5)%3&&(x-5)!=1&&(x-5)!=4&&(x-5)>0)
		{
			std::cout<<"YES"<<'\n'<<"1 4 "<-5<<'\n';
			continue;
		}
		if((x-7)%3&&(x-7)!=2&&(x-7)!=5&&(x-7)>0)
		{
			std::cout<<"YES"<<'\n'<<"2 5 "<-7<<'\n';
			continue;
		}
		std::cout<<"NO"<<'\n';
	}
	return 0;
}

但其实经过分析可以发现，只需要上面两个if语句就够了，n-3和n-5已经覆盖了所有情况。

 常规循环

因为思路比较简单我就直接复制的别人的代码，枚举前两个数，范围是1-13，然后对n-i-j进行判断就行。

#define ll long long
#include
using namespace std;
 
void solve(){
    ll n;cin>>n;
    
    for(ll i=1;i<13;i++){
        for(ll j=1;j<13;j++){
            ll z=n-i-j;
            
            if(z>0 && i!=j && i!=z && j!=z && i%3!=0 && j%3!=0 && z%3!=0){
                cout<<"Yes"<<"\n";
                cout<" "<" "<"\n";
                return;
            }
        }
    }
    
    cout<<"No"<<"\n";
}
 
int main(){
    ll n;cin>>n;
    
    while(n--)solve();
}

Problem - B - Codeforces

题目仍然是t个测试点

题目给出三个点p，a，b，要求以a和b分别为圆心，以w为半径做两个圆

要求o到p在圆上有路

思路分析：

分成两种情况进行讨论：

1.o，p在同一圆上

这种情况一定满足o到p在圆上有路，只要讨论哪个点作为圆心就好了。

要求两点在同一圆上，也就是要取圆心到o，p最大的那个距离作为半径

s1=min(max(点o到a的距离，p到a的距离），max(点o到b的距离，p到b的距离））

2.o，p不在同一圆上

这种情况下想要满足题意还需要满足条件：两圆相切

s2=(max(点a到点b的距离/4，min(max(点o到a的距离，p到b的距离），max(点o到b的距离，p到a的距离）））

#include
using namespace std;
int dis(int x1,int y1,int x2,int y2)
{
	return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
} 
signed main()
{
	int t;
	std::cin>>t;
	while(t--)
	{
		int p1,p2;
		int x1,y1;
		int x2,y2;
		std::cin>>p1>>p2>>x1>>y1>>x2>>y2;
		//只要源点和p都在圆上 
		//
		double s1=min(max(dis(p1,p2,x1,y1),dis(0,0,x1,y1)),
				   max(dis(p1,p2,x2,y2),dis(0,0,x2,y2)));
		double hh=(double)dis(x1,y1,x2,y2)/4;
		double s2=max(hh,
				   (double)min(max(dis(p1,p2,x1,y1),dis(0,0,x2,y2) ),
				       max(dis(p1,p2,x2,y2),dis(0,0,x1,y1))
				   )
				   );
	    double d=min(s1,s2);
		d=sqrt(d);
		printf("%.10f\n",d);
	}
	return 0;
}

Problem - C - Codeforces

题目大意：

可喜可贺终于看懂了题目。

 如果要一直变换s并且每一轮都拼接字符串将会非常麻烦，因此我们选择预处理数据n，对比字符串长度求出将要删cnt个字母才能得出答案。

因此，我们遍历字符串，如果当前字符比栈顶的字符小就出栈，cnt--，如此反复直到cnt为0。

这时cnt为0，我们按顺序依次把s里剩余的字符压入栈内，下标为n-1的字符就是答案。

#include
typedef long long LL;
 
void solve()
{
	LL n;
	std::string s;
	std::cin>>s>>n;
	int len=s.length();
	int cnt;//要删几个 
	while(n>len)
	{
		n-=len;
		len--;
		cnt++; 
	}//要输出第n个 
	std::vector<char> st;
	
	for(int i=0;ilength();i++)
	{
		while(!st.empty()&&cnt&&s[i]back())
		{
			st.pop_back();
			cnt--;
		}
		st.push_back(s[i]);
	}
	std::cout<-1];
}
signed main()
{
	int t;
	std::cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

Problem - D - Codeforces

我的绝望震耳欲聋。。

---

自己尝试了800次，怎么都觉得逻辑是对的但却超时，知道了做大数除法要用逆元 ，这时才真正理解了逆元的作用。

逆元的作用 一句话就是，将除法改为乘法； 例如 求 (A / B) %p ；在B的值非常大的情况下，B作为除数，极有可能会爆精度；除数不能太大；所以我们可以把他转化为乘法来解决； (a/b)mod m = (a/b)*1mod m = (a/b)bc mod

但本蒟蒻的代码不知道为何最后还是会爆，所以借鉴（照抄）了别人。D. Monocarp and the Set_阿根廷必胜的博客-CSDN博客

题目大意：

给定m，n，m代表字符串长度为m-1，有n条操作

 首先输出有几种可能的排序

然后对每次操作，输入x和字符c，把x位置上的字符替换为c，然后输出此时字符串可能的排序数。

思路：

我们将字符串倒着看，如果当前符号为>或<，则此字符只有一种可能。如果当前字符为？，就有i-2种可能，我们把它累乘就行了。

需要注意的是第一个字符串如果为？，ans*0=0，因为我们后续要替换，0除以任何数都为0 ，直接这样会造成不少的麻烦。

但是注意，ans=0只会在a[0]=？的情况下发生，因此我们用ans记录从1-m-2的情况数，对0位置进行单独讨论。

#include
#define int long long
const int mod = 998244353;
int qpow(int a, int b)//求逆元 
{
	int res = 1;
	while (b)
	{
		if (b & 1) res = res * a % mod;
		b >>= 1;
		a = a * a % mod;
	}
	return res;
}
signed main()
{
	std::ios_base::sync_with_stdio(0); std::cin.tie(0), std::cout.tie(0);
	int n,q;
	std::string s;
	std::cin>>n>>q>>s;
	
	int ans = 1;
	for (int i=1;i-1; i++) 
	{
		if (s[i]=='?') 
		{
			ans=ans*i%mod;
		}
	}
	std::cout << (s[0] == '?' ? 0 : ans) << '\n';
	while (q--)
	{
		int i;
		char c;
		std::cin >> i >> c;
		i--;
		if (i != 0 && s[i] == '?') 
		{
			ans = ans * qpow(i, mod - 2) % mod;
		}
		s[i] = c;
		if (i != 0 && s[i] == '?') 
		{
			ans = ans * i % mod;
		}
		std::cout << (s[0] == '?' ? 0 : ans) << '\n';
	}
	return 0;
}

 复习逆元

875. 快速幂 - AcWing题库

快速求出pow(a,k) mod p     时间复杂度O（log,k)

 

#include
typedef long long LL ;
LL qmi(int a,int k,int p)
{
    LL res=1;
    while(k)
    {
        if(k&1) res=(LL)res*a%p;
        k>>=1;
        a=(LL)a*a%p;
    }
    return res;
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0),std::cout.tie(0);
    
    int n;
    std::cin>>n;
    while(n--)
    {
        int a,k,p;
        std::cin>>a>>k>>p;
        std::cout<<qmi(a,k,p)<<'\n';
    }
    return 0;
}

876. 快速幂求逆元 - AcWing题库

#include
typedef long long LL;
LL qmi(int a,int k,int p)
{
	LL res=1;
	while(k)
	{
		if(k&1) res=(LL)res*a%p;
		k>>=1;
		a=(LL)a*a%p;	
	}
	return res;	
} 
signed main()
{
	int n;
	std::cin>>n;
	while(n--)
	{
		int a,p;
		std::cin>>a>>p;
		if(a%p==0) puts("impossible"); //a，p要求互质 
		else std::cout<<qmi(a,p-2,p)<<'\n';
	}
	
	return 0;
}