Codeforces Round #641 (Div. 2)

A n是奇數，f(n)一定是奇數；n是偶數，f(n)一定是2；

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200010;
int t;
ll n,k;
bool pr[N];
int main()
{
	cin>>t;
	while(t--)
	{
		cin>>n>>k;
		if((n&1)&&k)
		{
			bool flag=1;
			for(int i=3;i<=n/i;i++)
				if(n%i==0)
				{
					flag=0;
					n+=i;
					k--;
					break;
				}
			if(flag) 
			{
				n+=n;k--;
			}
		}
		cout<<n+k*2<<endl;
	}
	return 0;
}
           

B 選擇一堆下标，第i個下标可以被第i+1個下标整除，且該子序列是單增。

先預處理出來每個數的因子就好。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100010;
int t,n,a[N];
vector<int> ve[N];//ve[i]儲存能被i整除的數
int f[N];
void init()
{
	ll cnt=0;
	for(int i=2;i<N;i++)
	{
		ve[i].push_back(1);
		for(int j=2;j <= i/j;j++)
		{
			if((i%j)==0)
			{
				ve[i].push_back(j);
				if(i/j!=j) ve[i].push_back(i/j);
			}
		}
	}
}
int main()
{
	init();
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		memset(f,0,sizeof f);
		for(int i=1;i<=n;i++) scanf("%d",a+i);
		int ans=1;
		f[1]=1;
		for(int i=2;i<=n;i++)
		{
			f[i]=1;
			for(int j=0;j<ve[i].size();j++)
				if(a[i]>a[ve[i][j]])
					f[i]=max(f[i],f[ve[i][j]]+1);
			ans=max(ans,f[i]);
		}
		printf("%d\n",ans);
	}
	return 0;
}
           

C 資料這麼大肯定要分解質因數來求了。

假如n個數都含有質因子p，n個數的次幂分别是:m1,m2,m3…mn(已經從小到大排好序）。先求lcm，就是任意兩個數mi和mj( i!=j )的最大值，那麼會得到1個m2，2個m3…，再對他們求gcd，即這 (n-1)*n/2個數中最小值：m2，（n個數中次幂第二小）；

如果隻有n-1個數含最因子p，那麼令m1=0；那麼lcm還會得到1個m2，2個m3…，gcd還是取m2，（即n-1個數中次幂最小值）；

當少于n-1個數含有質因子p，m2=0，最終求得的次幂是0，忽略不計。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200010;
int t,n,a[N];
int res[N][2];//res[i][0]:i的次幂最小值，res[i][1]次幂第二小
vector<int> ve[N];
int num[N];
int main()
{
	scanf("%d",&n);
	int m=0;
	for(int i=1;i<=n;i++) scanf("%d",a+i),m=max(m,a[i]);
	for(int i=1;i<=n;i++)
	{
		int t=a[i];
		map<int,int> mp;
		for(int j=2;j<=t/j;j++)
		{
			int cnt=0;
			while(t%j==0)
			{
				t/=j;
				cnt++;
			} 
			if(cnt)
			{
				if(num[j]==0) res[j][0]=cnt; 
				else if(num[j]==1)
				{
					if(cnt>=res[j][0]) res[j][1]=cnt;
					else
					{
						res[j][1]=res[j][0];
						res[j][0]=cnt;
					}
 				}
 				else if(cnt<res[j][0])
 				{
 					res[j][1]=res[j][0];
 					res[j][0]=cnt;
				}
				else if(cnt<res[j][1])
				{
					res[j][1]=cnt;
				}
				num[j]++;
			}
		}
		if(t>1)
		{
			int cnt=1;
			if(num[t]==0) res[t][0]=cnt; 
			else if(num[t]==1)
			{
				if(cnt>=res[t][0]) res[t][1]=cnt;
				else
				{
					res[t][1]=res[t][0];
					res[t][0]=cnt;
				}
			}
			else if(cnt<res[t][0])
			{
				res[t][1]=res[t][0];
				res[t][0]=cnt;
			}
			else if(cnt<res[t][1])
			{
				res[t][1]=cnt;
			}
			num[t]++;
		}
	}
	ll ans=1;//答案沒有爆ll
	for(int i=2;i<=m;i++)
	{
		if(num[i]==n)
		{
			int t=res[i][1];
			while(t--)//用pow函數就會錯，貌似int型會重載
				ans=ans*i;
		}
		else if(num[i]==n-1)
		{
			int t=res[i][0];
			while(t--)
				ans=ans*i;
		}
	}
	printf("%lld",ans);
	return 0;
}
           

用優先隊列會短一些

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200010;
int t,n,a[N];
int res[N][2];
vector<int> ve[N];
int num[N];
priority_queue<int,vector<int>,greater<int> > q[N];
int main()
{
	scanf("%d",&n);
	int m=0;
	for(int i=1;i<=n;i++) scanf("%d",a+i),m=max(m,a[i]);
	for(int i=1;i<=n;i++)
	{
		int t=a[i];
		for(int j=2;j<=t/j;j++)
		{
			int cnt=0;
			while(t%j==0)
			{
				t/=j;
				cnt++;
			} 
			if(cnt)
			{
				num[j]++;
				q[j].push(cnt);
			}
		}
		if(t>1)
		{
			q[t].push(1);
			num[t]++;
		}
	}
	ll ans=1;
	for(int i=2;i<=m;i++)
	{
		if(num[i]==n)
		{
			q[i].pop();
			int t=q[i].top();
			while(t--)
				ans=ans*i;
		}
		else if(num[i]==n-1)
		{
			int t=q[i].top();
			while(t--)
				ans=ans*i;
		}
	}
	printf("%lld",ans);
	return 0;
}
           

補：

D 已知有n個數，每次操作可以選擇一個區間使得區間内中位數替換區間所有數，問進行若幹次操作是否可以将n個數都變為k。

首先一定要有k才可以操作成功；

① 操作兩個數時，隻有一個數等k一個數大于等于k或者兩個數都是k才能使得兩個數變為k；

② 操作三個數時隻有k是第二小時才能使三個數都變為k。

如果産生了長度大于等于兩個的連續k，那麼将連續區間向左或右擴充一個數，不論這個數是幾都可以把它變為k。

是以就要判斷是否能得到連續k了：

滿足①和②直接就可以了，那麼其他情況呢

如果兩個數都比k大的話，那麼操作之後兩個數一定相等且比k大（不用管具體是幾，隻用知道比k大就可以了），然後繼續向兩邊每次擴充一個數，就會得到一段連續區間一定比k大，直到擴充到k（k存在的情況下）就該操作k和這個區間與k相鄰的一個端點了，已知已經把這個端點變為比k大了，那麼滿足①，再以這兩個數為起點繼續擴充就可以了。

那麼如果是兩個比k大的數相隔一個數呢，不滿足上面的情況。但是操作這三個數一定可以将這三個數變得都比k大（還是不用管具體值），繼續上面的思路就一定可解。

綜上：當連續兩個數中大于等于k的個數大于等于2或者連續三個數中大于等于k的個數大于等于2，二者有一就可解。

#include<bits/stdc++.h>
using namespace std;
const int N=200010;
int n,t,k,a[N],b[N];

int main()
{
	cin>>t;
	while(t--)
	{
		cin>>n>>k;
		bool flag1=0,flag2=0;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
			if(a[i]==k) flag1=1;
			if(a[i]>=k) b[i]=1;
			else b[i]=0;
		}
		for(int i=1;i<n;i++)
			if(b[i]+b[i+1]>=2)
				flag2=1;
		for(int i=1;i<n-1;i++)	
			if(b[i]+b[i+1]+b[i+2]>=2)
				flag2=1;
		if(flag1&&(flag2||n==1))
			puts("yes");
		else puts("no");
	}
	return 0;
}