c题其实一般般吧,关于l什么的题意理解了好一会儿。暴力会超时,当然,优化很简单。
用了个q数组,q[i]代表i之前的素数的个数
还有s数组,s[i]代表第i个素数
之后就看着办吧
#include<iostream> #include<cstdio> using namespace std; int s[1200006]; int a,b; int k; int q[1200002]; bool f[1200006]; void go() { if(q[b+1]-q[a]<k) { cout<<-1<<endl; return; } int ma=s[q[a]+k]-a+1; // cout<<ma<<endl; for(int i=q[a]+1;i<=q[b+1]-k;i++) { if(ma<s[i+k]-s[i])ma=s[i+k]-s[i]; //cout<<s[i]<<" "<<ma<<endl; } if(ma<b-s[q[b+1]-k+1]+1)ma=b-s[q[b+1]-k+1]+1; cout<<ma<<endl; } int main() { f[2]=0; f[0]=1; f[1]=1; q[0]=0; q[1]=0; int num=0; for(int i=2;i<=1200001;i++) { q[i]=num; //cout<<q[i]<<endl; if(f[i]==0) { //cout<<i<<endl; s[++num]=i; for(int j=i*2;j<=1200001;j+=i)f[j]=1; } } while(scanf("%d%d%d",&a,&b,&k)!=EOF) { go(); } return 0; }
D题,题目巨啰嗦,各种看不懂。
将树分很多集合,集合的点并集就是原树的点,将每个集合作为新的“点”,有相同点的集合要连接,意思差不多很麻烦
就每边作为一个集合,统计共点,然后输出吧
#include<iostream> #include<cstdio> #include<vector> using namespace std; int main() { int n; int x[100001],y[100001]; vector<int>p[100001]; scanf("%d",&n); for(int i=1;i<n;i++) { scanf("%d%d",&x[i],&y[i]); p[x[i]].push_back(i); p[y[i]].push_back(i); } cout<<n-1<<endl; for(int i=1;i<n;i++)cout<<2<<" "<<x[i]<<" "<<y[i]<<endl; for(int i=1;i<=n;i++) { for(int j=0;j<p[i].size()-1;j++) { cout<<p[i][j]<<" "<<p[i][j+1]<<endl; } } return 0; }