Codeforces Round 777 (Div. 2) (C D分类讨论 E倍增+贪心)

A：

因为让数越大越好直接最长用21轮流即可

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;

const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;
int a[N];

void solve()
{
    cin>>n;
    int x=n/3;
    int y=n%3;
    if(y==0)
    {
        for(int i=1;i<=x;i++){
            cout<<"21";
        }
        cout<<"\n";
    }
    else if(y==1)
    {
        cout<<y<<"";
        for(int i=1;i<=x;i++){
            cout<<"21";
        }
        cout<<"\n";
    }
    else{
       // cout<<y<<"";
        for(int i=1;i<=x;i++){
            cout<<"21";
        }
        cout<<y<<"";
        cout<<"\n";
    }
}

signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t=1;
 
    cin>>t;
    while(t--) solve();
}

B：写了个很暴力的二分加前缀和...

实际做法是观察到如果是不合法的矩形一定存在2*2的矩阵和是3

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;

const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;
int a[110][110];

void solve()
{
    cin>>n>>m;
    vector<vector<int>> s(n+1,vector<int>(m+1));
    vector<vector<int>> row(n+1,vector<int>(m+1));
    vector<vector<int>> col(n+1,vector<int>(m+1));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
        {
            char c;
            cin>>c;
            a[i][j]=c-'0';
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
            row[i][j]=row[i][j-1]+a[i][j];
            col[i][j]=col[i-1][j]+a[i][j];
           // cout<<s[i][j]<<"  ";
        }
      //  cout<<"\n";
    }
  
    vector<vector<bool>> st(n+1,vector<bool>(m+1));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]==0) continue;
            int l=1,r=j;
            while(l<r)
            {
                int mid=l+r>>1;
                if(row[i][j]-row[i][mid-1]>=j-mid+1) r=mid;
                else l=mid+1;
            }
            int x1,y1,x2,y2;
            y1=l;
            
            l=j,r=m;
            while(l<r)
            {
                int mid=l+r+1>>1;
                if(row[i][mid]-row[i][j-1]>=mid-j+1) l=mid;
                else r=mid-1;
            }
            y2=l;
            
            l=1,r=i;
            while(l<r)
            {
                int mid=l+r>>1;
                if(col[i][j]-col[mid-1][j]>=i-mid+1) r=mid;
                else l=mid+1;
            }
            x1=l;
            
            l=i,r=n;
            while(l<r)
            {
                int mid=l+r+1>>1;
                if(col[mid][j]-col[i-1][j]>=mid-i+1) l=mid;
                else r=mid-1;
            }
            x2=l;
            
            if(s[x2][y2]+s[x1-1][y1-1]-s[x2][y1-1]-s[x1-1][y2]!=(x2-x1+1)*(y2-y1+1)){
                cout<<"NO\n";
                //cout<<x2<<" "<<y2<<" "<<x1<<" "<<y1<<"\n";
                return ;
            }
        }
    }
    
    cout<<"YES\n";
}

signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t=1;
 
    cin>>t;
    while(t--) solve();
}

C：

特判第一个点就行了

然后用01矩阵和

0

1

矩阵覆盖即可

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;

const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;
char a[110][110];

void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            cin>>a[i][j];
    }
    if(a[1][1]=='1'){
        cout<<"-1\n";return ;
    }
    vector<array<int,4>> res;
    for(int i=n;i>=1;i--){
        for(int j=m;j>=1;j--){
            if(a[i][j]=='0') continue;
            if(j==1){
                res.push_back({i-1,j,i,j});
            }
            else res.push_back({i,j-1,i,j});
        }
    }
    cout<<res.size()<<"\n";
    for(auto e:res) cout<<e[0]<<" "<<e[1]<<" "<<e[2]<<" "<<e[3]<<"\n";
}

signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t=1;
 
    cin>>t;
    while(t--) solve();
}

D：

分类讨论这里就不讲了

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;

const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;
int a[110][110];
bool primes(int x){
    for(int i=2;i<=x/i;i++){
        if(x%i==0) return false;
    }
    return true;
}
void solve()
{
    int x,d;
    cin>>x>>d;
    int res=0,cnt=0;
    int n=x;
    while(x%d==0)
    {
        cnt++;
        x/=d;
    }
    if(cnt<=1){ cout<<"NO\n";return ;}
    if(!primes(x)){ cout<<"YES\n";return ;}
    if(primes(d)){ cout<<"NO\n";return ;}
    
    if(cnt>=4){ cout<<"YES\n";return ;}
    
    if(cnt==2){ cout<<"NO\n";return ;}
    if(d==x*x) { cout<<"NO\n";return ;}
    cout<<"YES\n";
}

signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t=1;
 
    cin>>t;
    while(t--) solve();
}

E：

首先我们是能计算经历了多少轮的

因为p数组有x个不同元素，那么每轮就有n-x个人出去了

然后a数组最大的数mx

所以k=（mx-n）/(n-x)就是论数了，mx记得减n，因为本来就有n个人

然后倍增求出来每个位置最后会到哪个位置

求出来之后就会发现有些位置会有不同的初始位置到达

因为字典序最小，所以直接让当前可以到达的位置里面的最小的位置等于当前最终结果的数即可

对于其他位置，因为不影响结果，所以直接从还存在的位置放进去第一个大于当前数即可

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;

const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;
int p[N],a[N];
int to[N][40];
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>p[i],to[i][0]=p[i];
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=30;i++){
        for(int j=1;j<=n;j++){
            to[j][i]=to[to[j][i-1]][i-1];
        }
    }
    
	int k = (*max_element(a+1, a+1+n) - n) / 
	    (n - unordered_set<int>(p+1, p+1+n).size());
	    
	 int dest[n+1];
	 for(int i=1;i<=n;i++) dest[i]=i;
	 for(int i=30;i>=0;i--){
	     if(k>>i&1){
	         k-=(1<<i);
	         for(int j=1;j<=n;j++){
	             dest[j]=to[dest[j]][i];
	         }
	     }
	 }
	 set<int> s;
	 int ans[n+1]={0};
	 for(int i=1;i<=n;i++) s.insert(i);
	 int vis[n+1]={0};
	 
	 for(int i=1;i<=n;i++){
	     if(vis[dest[i]]) continue;
	     vis[dest[i]]=1;
	     ans[i]=a[dest[i]];
	     s.erase(ans[i]);
	 }
	 
	 for(int i=1;i<=n;i++){
	     if(!ans[i]){
	         auto it=s.lower_bound(a[dest[i]]);
	         ans[i]=*it;
	         s.erase(it);
	     }
	     
	 }
	 for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
	 
}

signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t=1;
 
    //cin>>t;
    while(t--) solve();
}