Educational Codeforces Round 89 (A-D)

~~比赛没打，来补题辣。~~

A. Shovels and Swords

思路：数学，高中线性规划搞一下，由于 $a,b$ 对称性，可以默认 $a\leq b$ ，然后分两种情况搞一下就行了。

$ans=\begin{cases}\dfrac{a+b}{3},b\leq2a\\a\ \ \ \ \ \ \ \ ,otherwise\end{cases}$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first 
#define se second
int main(){
    int t;
    cin>>t;
    while(t--){
        int a,b;
        cin>>a>>b;
        if(a>b) swap(a,b); 
        if(b<=2*a) cout<<(a+b)/3<<endl;
        else cout<<a<<endl;
    } 
    return 0;
}

B. Shuffle

思路：简单贪心，找到一个含 $x$ 的区间，然后不断更新区间长度即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first 
#define se second
int main(){
    int t;
    cin>>t;
    while(t--){
        int n,x,m;
        cin>>n>>x>>m;
        int L=0,R=0,f=0;
        for(int i=1;i<=m;i++){
            int l,r;
            cin>>l>>r;
            if((x>=l&&x<=r)&&!f){
                 L=l,R=r,f=1;
                 continue;    
            }
            if(f){
                if(l>R||r<L) continue;
                else L=min(L,l),R=max(R,r);
            }            
        }
        cout<<R-L+1<<endl;
    } 
    return 0;
}

C. Palindromic Paths

思路：贪心，因为是回文串，所以走 $k$ 步的点要与走 $n+m-2-k$ 步的点相同，

简单证明一下：

$\begin{pmatrix} 1 & 0 & 1 & 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 0 & 1 & 1 & 0\\ 1 & 1 & 1 & 1 & 1 & 0 & 1 \end{pmatrix}$

比如走两步的点有 $(1,3),(2,2),(3,1)$ ，走 $n+m-2-2=6$ 步的点有：

$(1,7),(2,6),(3,5)$ .

显然可以从 $(3,1)走到(3,5).$ 所以 $num[3][1]=num[3][5]$ . (1)

同理： $(2,2)可以走到(2,6),(3,5) \rightarrow num[2][2]=num[2][6]=num[3][5]$ . (2)

$(1,3)可以走到(1,7),(2,6),(3,5)\\ \Rightarrow num[1][3]=num[1][7]=num[2][6]=num[3][5] \quad(3)$

联立 $(1),(2),(3)$ 可以知道所有数要相等。

然后每步贪心判断一下选0还是1即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=65;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first 
#define se second
int a[N][2];
int main(){
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        mst(a);
        for(int i=1;i<=n;i++)
            for(int j=1,x;j<=m;j++){
                 cin>>x;
                 a[i+j-2][x]++;
            }
        int ans=0;
        for(int i=0,j=n+m-2;i<j;i++,j--)
            ans+=min(a[i][0]+a[j][0],a[i][1]+a[j][1]);
        printf("%d\n",ans);
    } 
    return 0;
}

D. Two Divisors

思路：数论知识，

若两质数 $(p,q)=1\rightarrow(p^{k_1},q^{k_2})\\=(p^{k_1}+q^{k_2},p^{k_1})\\=(p^{k_1}+q^{k_2},q^{k_2})\\=(p^{k_1}+q^{k_2},p^{k_1}\times q^{k_2})=1,(k1,k2为正整数)$ .

若数 $x$ 只有一个质因子，说明它的因数都是 $p$ 的倍数，即gcd最大为 $p^k>1$ 。
所以对数 $x$ 进行质因数分解：得到 $p_1^{k_1}\times\dots p_m^{k_m}=x$ .

$(p_1^{k_1}\dots p_{m-1}^{k_{m-1}}+p_m^{k_m},p_m^{k_m})=1$

这里取 $p_m$ 是为了加速质因数分解。

所以进行素数筛预处理一下，然后判断因子是否为1即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+10,M=1e7+5;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first 
#define se second
inline void read(int &x){ 
    x=0;int w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    for(;ch>='0'&&ch<='9';ch=getchar())
        x=(x<<3)+(x<<1)+(ch&15);
    x*=w; 
}
int p[M];
PII ans[N];
void fun(){
    int n=1e7;
    for(int i=2;i<=n;i++)
         if(!p[i])
            for(int j=i;j<=n;j+=i) p[j]=i;
}
int main(){
    int n;
    fun();
    read(n);
    for(int i=1,x;i<=n;i++){
         read(x);
         int a=p[x],y=1;
         while(x%a==0){
              x/=a,y*=a;
         }
         if(x==1) x=y=-1;
         ans[i]={x,y};
    }
    for(int i=1;i<=n;i++) printf("%d ",ans[i].fi);
    puts("");
    for(int i=1;i<=n;i++) printf("%d ",ans[i].se);
    return 0;
}

待补 $\dots\dots$