A. 小心别写疵了，这种题容易被hack
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int main(){
IO;
int t;cin>>t;
while(t--){
ll n;cin>>n;
int cnt = 0;
while(n%2==0||n%3==0||n%5==0){
while(n%2==0) n>>=1,cnt++;
if(n%3==0) n/=3,n*=2,cnt++;
else if(n%5==0) n/=5,n*=4,cnt++;
}
if(n==1) cout <<cnt<<'
';
else cout <<-1<<'
';
}
return 0;
}
B. %题
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1000;
int a[3];
int main(){
IO;
int t;cin>>t;
while(t--){
memset(a,0,sizeof(a));
int n;cin>>n;
forn(i,n){
int x;cin>>x;
a[x%3]++;
}
int x = min(a[1],a[2]);
int ans = a[0]+x;
a[1]-=x,a[2]-=x;
ans+=a[1]/3;
ans+=a[2]/3;
cout <<ans<<'
';
}
return 0;
}
C 分组之后匹配，有点类似2019湘潭ccpc E题，出问题的同学可以补完去做一下（在HDU的重现赛里)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int maxn = 5e5+5;
int main(){
IO;
int n;cin>>n;
set<int>a[100];
forn(i,n){
int x;cin>>x;
if(x==4) a[0].insert(i);
else if(x==8) a[1].insert(i);
else if(x==15) a[2].insert(i);
else if(x==16) a[3].insert(i);
else if(x==23) a[4].insert(i);
else a[5].insert(i);
}
int ans = 0;
forn(j,n/6){
int l = -1,cnt=0;
bool ok = 0;
forn(i,6){
while(a[i].size()){
int x = *a[i].begin();
if(x>l){
l=x,cnt++;
a[i].erase(a[i].begin());
break;
}
a[i].erase(a[i].begin());
}
if(cnt==6) ok = 1;
}
if(ok) ans++;
}
cout <<n-(ans*6)<<'
';
return 0;
}
D. 素数筛因子筛+打表+思维
思路：O（n）的素数筛是可以筛出来每个素数和每个数的最小因子。
题中数x分两种：
- 素数 添加prime[x]
- 和数 添加其最大因子x/factor[x]
我们打一个表b[x]=如上两种情况。那么下一步就是准确的筛出来正确的数。
我们可以发现b[3]=5 b[9] =3如果我们用3筛掉5 再筛出来9显然是不方便的，所以我们倒着来。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int maxn = 3e6 + 5;
int prime[maxn],factor[maxn],a[maxn],b[maxn];
int sieve(int n){
int p = 0;
for (int i = 2; i <= n; i++){
if (!factor[i]){
prime[p++] = i,factor[i] = i;
}
for (int j = 0; j < p && prime[j] * i <= n; j++){
factor[prime[j] * i] = prime[j];
if (!(i % prime[j]))
break;
}
}
return p;
}
multiset<int>s;
int main(){
IO;
int len = sieve(maxn-5),n,p = 0;
for1(i,200000){
if(i==1) continue;
if(i==prime[p]){
p++;
b[prime[i-1]] = i;
}else{
int x = factor[i];
x = i/x;
b[i] = x;
}
}
cin>>n;
n*=2;
forn(i,n){
int x;cin>>x;
s.insert(x);
}
vector<int>ans;
forn(i,n/2){
int z = *s.rbegin();
//cerr<<z<<' '<<b[z]<<'
';
int y = b[z];
if(z%b[z]==0) ans.push_back(z);
else ans.push_back(b[z]);
s.erase(s.find(z));
s.erase(s.find(b[z]));
}
for(auto x:ans) cout <<x<<' ';
cout <<'
';
return 0;
}
E bfs或dfs01染色
思路：
我们目的是让未被选中点和被选中的点至少一条边。那么bfs的思路就很形象。第一个点设为0，直接相连的点都为1，然后与这些直接相连的点的其他点为0，再往后为1，然后和我们取为1的点和取为0的点都可以让未被选的点跟被选的点有连线。
既然n个点都被分为0或1，那么我们取最小的那一个点的集合就是正确答案。
同理用dfs（写起来快点）也可以
dfs：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int maxn = 2e5+5;
bool vis[maxn];
vector<int>e[maxn],c[2];
void dfs(int cur,bool now){
c[now].push_back(cur);
vis[cur] = 1;
for(auto x:e[cur]) if(!vis[x]) dfs(x,now^1);
return;
}
int main(){
IO;
int t;cin>>t;
while(t--){
int n,m;cin>>n>>m;
for1(i,n) e[i].clear(),vis[i] = 0;
for1(i,m){
int x,y;cin>>x>>y;
e[x].push_back(y);
e[y].push_back(x);
}
c[0].clear();c[1].clear();
dfs(1,0);
if(c[0].size()>c[1].size()) swap(c[0],c[1]);
cout <<c[0].size()<<'
';
for(auto x:c[0]) cout <<x<<' ';
cout <<'
';
}
return 0;
}
F 应该是个DP 明早补 晚安
托更 cf崩了我复习考试 后天见