星空第一OI学院 举办的团队邀请赛 「XKOI」星空学院 Round 2 明天开始。
思路：
记录每个点与其相连的边的个数，在计算与环相连的边的个数时，只需要求和并减去环自身的边即可。注意需要减 $6$ 因为环上的每条边都重复计算了两次。
由于数据范围小，直接三层循环枚举每一个环并求出最小值即可。
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int N=4005;
int n,m;
int g[N][N],cnt[N];
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
cnt[u]++;
cnt[v]++;
g[u][v]=g[v][u]=1;
}
int minx=0x3f3f3f3f;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(!g[i][j])continue;
for(int k=1;k<=n;k++){
if(!g[i][k])continue;
if(!g[j][k])continue;
minx=min(minx,cnt[i]+cnt[j]+cnt[k]);
}
}
}
if(minx==0x3f3f3f3f)printf("-1\n");
else printf("%d\n",minx-6);
return 0;
}
思路：
首先，质数必须询问，不然该质数和 $1$ 的回答就是相同的。
其次，一个质数的若干次方需要进行询问，因为整除 $p_i^k$ 不代表整除 $p_i^{k+1}$ ，如果不判断 $p_i^k$ ，那么 $p_i^{k-1}$ 和 $p_i^k$ 的回答是相同的。
除了上述讨论的数都可以转换成$p_1^{a_1}\times p_2^{a_2}\times … \times p_k^{a_k}$的形式。整除 $a$ 且整除 $b$ 自然整除 $a\times b$，所以无需询问。
最后，统计所需询问的个数并输出即可。
代码如下：
#include <bits/stdc++.h>
using namespace std;
int n;
int a[1001],b[1001],cnt;
int c[1001],tot;
int main(){
cin>>n;
for(int i=2;i<=n;i++){
if(!b[i]){
a[++cnt]=i;
c[++tot]=i;
int x=i;
while(x*i<=n){
c[++tot]=x*i;
x=x*i;
}
}
for(int j=1;a[j]<=n/i;j++){
b[i*a[j]]=1;
if(i%a[j]==0){
break;
}
}
}
cout<<tot<<endl;
for(int i=1;i<=tot;i++){
cout<<c[i]<<" ";
}
return 0;
}
原理：main函数的递归
将01背包代码分为4个部分，用t记录当前的状态
部分一
当t=0时，读入n和m
cin>>n>>m;
代码如下：
int main(){
......
if(t==0){
cin>>n>>m;
t=1;
main();
t=2;
main();
return 0;
}
......
}
部分二
当t=1时，读入a[]和b[]
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
}
可以用递归的方式进行循环，代码如下：(i初始值为1)
int main(){
......
if(t==1){
if(i>n){
t=2;
return main();
}
cin>>a[i]>>b[i];
i++;
main();
}
......
}
部分三和部分四
for(int i=1;i<=n;i++){
for(int j=m;j>=a[i];j--){
f[j]=max(f[j],f[j-a[i]]+b[i]);
}
}
cout<<f[m];
当t=2时，完成外层循环的功能，特别的，在循环结束时输出结果
当t=3时，完成内层循环的功能
int main(){
if(t==2){
if(i>n){
printf("%d\n",f[m]);
return 0;
}
t=3;j=m;
main();
t=2;i++;
return main();
}else if(t==3){
if(j<a[i]){
return 0;
}
f[j]=max(f[j],f[j-a[i]]+b[i]);
j--;
return main();
}
}
完整代码如下：
#include<bits/stdc++.h>
using namespace std;
int t=0;//表示状态
int n,m,i,j;//n为物品个数，m为背包容量
int a[20005],b[20005],f[20005];//a表示代价，b表示价值
int main(){
if(t==0){
scanf("%d%d",&n,&m);
t=1;i=1;
main();
t=2;i=1;
return main();
}else if(t==1){
if(i>n){
return 0;
}
scanf("%d%d",&a[i],&b[i]);
i++;
main();
}else if(t==2){
if(i>n){
printf("%d\n",f[m]);
return 0;
}
t=3;j=m;
main();
t=2;i++;
return main();
}else if(t==3){
if(j<a[i]){
return 0;
}
f[j]=max(f[j],f[j-a[i]]+b[i]);
j--;
return main();
}
}
分享
不用循环的01背包代码
原理：main函数的递归
将01背包代码分为4个部分，用t记录当前的状态
部分一
当t=0时，读入n和m
cin>>n>>m;
代码如下：
int main(){
......
if(t==0){
cin>>n>>m;
t=1;
main();
t=2;
main();
return 0;
}
......
}
部分二
当t=1时，读入a[]和b[]
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
}
可以用递归的方式进行循环，代码如下：(i初始值为1)
int main(){
......
if(t==1){
if(i>n){
t=2;
return main();
}
cin>>a[i]>>b[i];
i++;
main();
}
......
}
部分三和部分四
for(int i=1;i<=n;i++){
for(int j=m;j>=a[i];j--){
f[j]=max(f[j],f[j-a[i]]+b[i]);
}
}
cout<<f[m];
当t=2时，完成外层循环的功能，特别的，在循环结束时输出结果
当t=3时，完成内层循环的功能
int main(){
if(t==2){
if(i>n){
printf("%d\n",f[m]);
return 0;
}
t=3;j=m;
main();
t=2;i++;
return main();
}else if(t==3){
if(j<a[i]){
return 0;
}
f[j]=max(f[j],f[j-a[i]]+b[i]);
j--;
return main();
}
}
完整代码如下：
#include<bits/stdc++.h>
using namespace std;
int t=0;//表示状态
int n,m,i,j;//n为物品个数，m为背包容量
int a[20005],b[20005],f[20005];//a表示代价，b表示价值
int main(){
if(t==0){
scanf("%d%d",&n,&m);
t=1;i=1;
main();
t=2;i=1;
return main();
}else if(t==1){
if(i>n){
return 0;
}
scanf("%d%d",&a[i],&b[i]);
i++;
main();
}else if(t==2){
if(i>n){
printf("%d\n",f[m]);
return 0;
}
t=3;j=m;
main();
t=2;i++;
return main();
}else if(t==3){
if(j<a[i]){
return 0;
}
f[j]=max(f[j],f[j-a[i]]+b[i]);
j--;
return main();
}
}
推公式+暴力
时间复杂度$O(n)$
#include<bits/stdc++.h>
using namespace std;
int n;
int a[100001],b[100001],c[100001];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
b[i]=a[i]>>1;
c[i]=(a[i]+1)>>1;
}
int ans=0,s1=0,s2=0;
for(int i=1;i<=n;i++){
if(b[i]!=b[i-1]){
s1=0;
}
if(c[i]!=c[i-1]){
s2=0;
}
s1++;s2++;
ans=max(ans,max(s1,s2));
}
printf("%d\n",ans);
return 0;
}
活动打卡代码
AcWing 2058. 笨拙的手指（每日一题）
#include<bits/stdc++.h>
using namespace std;
const int N=10005;
char str1[N],str2[N],str3[N];
int main(){
scanf("%s",str1);
scanf("%s",str2);
if(str1[0]=='0'){
int sum=1;
for(int i=1;i<strlen(str1);i++){
sum=sum*2+str1[i]-'0';
}
printf("%d\n",sum);
return 0;
}
int sum=0,len=strlen(str1);
for(int i=0;i<len;i++){
sum=sum*2+str1[i]-'0';
}
for(int i=1;i<len;i++){
int _sum=sum+pow(2,len-i-1)*(str1[i]=='0'?1:-1);
int cnt=0,__sum=_sum;
for(int j=strlen(str2)-1;j>=0;j--){
if(_sum%3!=str2[j]-'0')cnt++;
_sum/=3;
}
if(cnt==1){
printf("%d\n",__sum);
}
}
return 0;
}
活动打卡代码
AcWing 1249. 亲戚（每日一题）
#include<bits/stdc++.h>
using namespace std;
int s[100010]={0};
int find(int x){
if(s[x]==x) return x;
return s[x]=find(s[x]);
}
int n,m,p;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) s[i]=i;
while(m--){
int x,y;
scanf("%d%d",&x,&y);
s[find(y)]=s[find(x)];
}
scanf("%d",&p);
while(p--){
int x,y;
scanf("%d%d",&x,&y);
if(s[find(x)]==s[find(y)]) printf("Yes\n");
else printf("No\n");
}
return 0;
}
活动打卡代码
AcWing 1497. 树的遍历（每日一题）
#include<bits/stdc++.h>
using namespace std;
const int N=10005;
int n,son[N][2];
int str1[N],str2[N];
void print(int k){
queue<int>q;
q.push(k);
while(!q.empty()){
int fa=q.front();
q.pop();
printf("%d ",fa);
if(son[fa][0]!=0)q.push(son[fa][0]);
if(son[fa][0]!=0)q.push(son[fa][1]);
}
}
void dfs(int root,int l1,int r1,int l2,int r2,int b){
if(l1>r1)return;
son[root][b]=str1[r1];
for(int i=l2;i<=r2;i++){
if(str2[i]==str1[r1]){
dfs(str1[r1],l1,l1+i-l2-1,l2,i-1,0);
dfs(str1[r1],r1-r2+i,r1-1,i+1,r2,1);
}
}
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&str1[i]);
}
for(int i=0;i<n;i++){
scanf("%d",&str2[i]);
}
dfs(0,0,n-1,0,n-1,0);
print(son[0][0]);
return 0;
}
活动打卡代码
AcWing 3777. 砖块（每日一题）
#include<bits/stdc++.h>
using namespace std;
int t,n;
char a[1000000];
int b[1000000];
int c[1000000],cnt;
int main(){
scanf("%d",&t);
while(t--){
scanf("%d",&n);
scanf("%s",a);
for(int i=0;i<n;i++){
if(a[i]=='W')b[i]=1;
else b[i]=0;
}
cnt=0;
for(int i=0;i<n-1;i++){
if(b[i])continue;
b[i]=!b[i];
b[i+1]=!b[i+1];
b[i+2]=!b[i+2];
c[++cnt]=i+1;
}
if(!b[n-1]){
puts("-1");
}else if(cnt==0){
puts("0");
}else{
printf("%d\n",cnt);
for(int i=1;i<=cnt;i++){
printf("%d ",c[i]);
}
puts("");
}
}
return 0;
}
