A. Fake NP
题意：给你l,r，让你输出[l,r]里面除1以外的，出现因子数量最多的那个数。
题解：如果l==r输出l，否则都输出2
#include<bits/stdc++.h>
using namespace std;
int main(){
int l,r;
cin>>l>>r;
if(r-l==0){
cout<<l<<endl;
return 0;
}
int ans = 0;
int num = 0;
for(int i=2;i<=10000;i++){
if(r/i-(l-1)/i>num)
num = r/i-(l-1)/i,ans = i;
}
cout<<ans<<endl;
}
B. 3-palindrome
题意：给你n，你需要构造一个长度为n的，不存在长度为3的回文串的串。
题解：aabbaabbaabbaabb这样一直构造下去就好了。
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
if(i%4==0)cout<<"a";
else if(i%4==1)cout<<"a";
else if(i%4==2)cout<<"b";
else if(i%4==3)cout<<"b";
}
cout<<endl;
}
C. Find Amir
题意：从i到j的代价是(i+j)%(n+1)，问你经过所有点的最小代价是多少
题解：显然就是(n-1)/2
#include<bits/stdc++.h>
using namespace std;
int main(){
long long ans = 0;
long long n;
cin>>n;
if(n==1){
cout<<"0"<<endl;
return 0;
}
ans = (n/2-1);
if(n%2==1)ans++;
cout<<ans<<endl;
}
D. Minimum number of steps
题意：你的每一次操作，会使得一个ab变成bba，问你最多进行多少次操作
题解：显然最后的答案会变成bbbbbbbaaaaaaa，那么我们倒着看，每次遇到一个b，就会使得b的数量加一，遇到一个a，就会花费当前b的数量，移动到最后，并且使得b的数量翻倍。
#include<bits/stdc++.h>
using namespace std;
const long long mod = 1e9+7;
long long ans = 0;
string s;
int main(){
cin>>s;
reverse(s.begin(),s.end());
long long B = 0;
long long A = 0;
for(int i=0;i<s.size();i++){
if(s[i]=='a'){
ans = (ans + B)%mod;
B = B * 2LL % mod;
}else{
B = (B + 1)% mod;
}
}
cout<<ans<<endl;
}
E. Ice cream coloring
题意：给你一棵树，然后树上的每个点有一堆颜色，保证每个颜色都会组成一个联通块。现在让你输出一个方案，使得出现在同一个点的颜色都各不相同。
题解：如果不给你一棵树这个条件，那么这就是一个np问题。但是他给了，说明这就是个xjb贪心的问题……
首先最大的颜色数量，就是点的最大颜色数量。然后我们贪心的去涂颜色就好了。
但是有个数据：
3 2
1 1
1 2
2 1 2
1 3
2 3
所以我们得按照一定的顺序去涂颜色就行。
（好像这棵树的条件还是没用上。。。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5+7;
int n,m;
vector<int>E[maxn],G[maxn],H[maxn];
int vis[maxn];
int ans[maxn];
map<int,int>H2[maxn];
queue<int>Q;
int tot;
void solve(int i){
for(int j=0;j<E[i].size();j++){
int v = E[i][j];
if(ans[v]!=0)continue;
while(H2[i][tot]==1)tot++;
ans[v]=tot;
H2[i][tot]=1;
for(int k=0;k<H[v].size();k++){
if(H2[H[v][k]][tot]==0){
Q.push(H[v][k]);
}
H2[H[v][k]][tot]=1;
}
}
vis[i]=1;
}
int main(){
scanf("%d%d",&n,&m);
int Ans = 0;
for(int i=1;i<=n;i++){
int p;
scanf("%d",&p);
for(int j=0;j<p;j++){
int x;
scanf("%d",&x);
E[i].push_back(x);
H[x].push_back(i);
}
}
for(int i=1;i<n;i++){
int x,y;
scanf("%d%d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
for(int i=1;i<=n;i++){
tot = 1;
if(vis[i])continue;
solve(i);
while(!Q.empty()){
int now = Q.front();
tot = 1;
Q.pop();
if(vis[now])continue;
solve(now);
}
}
for(int i=1;i<=m;i++)
if(ans[i]==0)
ans[i]=1;
for(int i=1;i<=m;i++)
Ans=max(Ans,ans[i]);
cout<<Ans<<endl;
for(int i=1;i<=m;i++)
cout<<ans[i]<<" ";
cout<<endl;
}