CF VP Day1 Codeforces Round #641 (Div. 2) A B C D E

CF VP Day1 Codeforces Round #641 (Div. 2) A B C D E

A. Orac and Factors

思路： 合数先加上最小质因子后续输出$2$，质数加上他本身，后续加上$2$。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
void solve(){
    int a,b;cin>>a>>b;bool ok=false;int mi;for(int i=2;i*i<=a;i++){
    if(a%i==0){
    ok=true;mi=i;break;}}if(ok){
    a+=mi;b--;a+=b*2;}else{
    a+=a;b--;a+=b*2;}cout<<a<<endl;
}
signed main(){
    int t=1;cin>>t;for(int i=1;i<=t;i++){
    solve();}return 0;
}

B. Orac and Models

思路： 线性$dp$，枚举i的因子$j$如果$a[i]>a[j]$，则$dp[i]=dp[j]+1$，答案为$max$。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N];
int dp[N];
void solve(){
    int n;cin>>n;int ma=1;for(int i=1;i<=n;i++){
    cin>>a[i];dp[i]=1;}for(int i=1;i<=n;i++){
    for(int j=1;j*j<=i;j++){
    if(i%j==0){
    if(a[i]>a[j])dp[i]=max(dp[i],dp[j]+1);if(a[i]>a[i/j])dp[i]=max(dp[i],dp[i/j]+1);ma=max(ma,dp[i]);}}}cout<<ma<<endl;
}
int main(){
    int t;cin>>t;while(t--){
    solve();}return 0;
}

C. Orac and LCM

思路： 推公式，见图。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
long long dp[N];
int a[N];
void solve(){
    int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];dp[n]=a[n];for(int i=n-1;i>=1;i--)dp[i]=gcd(dp[i+1],a[i]);long long ans=0;dp[n+1]=0;for(int i=1;i<=n;i++){
    ans=gcd(ans,(long long)lcm(a[i],dp[i+1]));}cout<<ans<<endl;
}
int main(){
    int t=1;// cin>>t;while(t--){
    solve();}return 0;
}

D. Orac and LCM

思路： 构造，如果在数组中没找到目标值一定是$no$，否则进行判断，判断每个目标值是否被区间$[左1，左2，X，右2，右1]$孤立，其左右两个数中一旦出现大于等于$X$的数，那么一定能形成最终全$X$数组，一个数需要特判。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N];
void solve(){
    int n,k;cin>>n>>k;for(int i=1;i<=n;i++)cin>>a[i];bool ok = false;for(int i=1;i<=n;i++){
    if(a[i]==k)ok=true;if(a[i]<k)a[i]=0;else if(a[i]==k)a[i]=1;else if(a[i]>k)a[i]=2;}if(!ok){
    cout<<"no"<<endl;return ;}if(n==1){
    cout<<"yes"<<endl;return ;}for(int i=1;i<=n;i++){
    for(int j=i+1;j<=n&&j-i<=2;j++){
    if(a[i]&&a[j]){
    cout<<"yes"<<endl;return ;}}    }cout<<"no"<<endl;return ;
}
int main(){
    int t;cin>>t;while(t--){
    solve();}return 0;
}

E. Orac and Game of Life

思路： 是一个很有意思的题，如果周边出现同色的，那么该块我们记为$good$，一定能每次$iteration$都变色，如果周边没有同色的那么该块我们记为$bad$，那么该块刚开始$iteration$必定不能变色，直到什么时候能变色呢？每个$good$块每次$iteration$可以使周边的$bad$的块变成$good$，那么我们只需通过多源$bfs$进行扩散，来记录每个$bad$块最少几次$iteration$之后会变成$good$块。然后与$p$结合，求出最终块色。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
char a[N][N];
using ll=long long ;
ll use[N][N];
int dx[]={
    1,-1,0,0};
int dy[]={
    0,0,1,-1};
int n,m,t;
typedef pair<int,int>PII;
queue<PII>q;
bool st[N][N];
void check(int x,int y){
    bool ok = false;for(int i=0;i<4;i++){
    int xx=x+dx[i];int yy=y+dy[i];if(xx<1||yy<1||xx>n||yy>m)continue;if(a[xx][yy]==a[x][y]){
    ok=true;}}if(ok){
    use[x][y]=0;st[x][y]=true;q.push({
    x,y});}
}
int main(){
    cin>>n>>m>>t;memset(use,0x3f,sizeof use);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
    check(i,j);}}while(q.size()){
    auto g=q.front();q.pop();int x=g.first,y=g.second;for(int i=0;i<4;i++){
    int xx=x+dx[i],yy=y+dy[i];if(xx<1||yy<1||xx>n||yy>m||use[xx][yy]!=0x3f3f3f3f3f3f3f3f||st[xx][yy])continue;use[xx][yy]=use[x][y]+1;q.push({
    xx,yy});}}while(t--){
    int x,y;ll q;cin>>x>>y>>q;int cnt;if(a[x][y]=='0')cnt=0;else cnt=1;if(use[x][y]>=q){
    cout<<cnt<<endl;}else{
    q-=use[x][y];q+=cnt;cout<<(q%2)<<endl;}}return 0;
}