A - Divide it!
能除以2就除以2，不能除以2再乘以一个$\frac{2}{3}$或$\frac{4}{5}$，再除以2就行
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n;
int main()
{
int Test;cin>>Test;
while(Test--)
{
cin>>n;
int ans=0;
while(n>1)
{
if((n%2)&&(n%3)&&(n%5)){ans=-1;break;}
while(n%2==0)n/=2,ans++;
if(n%3==0)n=n*2/3,ans++;
while(n%2==0)n>>=1,ans++;
if(n%5==0)n=n*4/5,ans++;
while(n%2==0)n>>=1,ans++;
}
printf("%d\n",ans);
}
return 0;
}
B - Merge it!
直接看除以3的余数：余数为0就不管，就看余数为1和2的怎么凑可以凑出最多的余数为0的数。
发现一个1和一个2就可以，剩下的1（或2）需要3个来凑。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
int n;
int a[105];
int cnt[5];
int main()
{
int Test;cin>>Test;
while(Test--)
{
cin>>n;mem(cnt,0);int ans=0;
for(int i=1;i<=n;++i)scanf("%d",&a[i]),a[i]%=3;
for(int i=1;i<=n;++i)cnt[a[i]]++;
int tmp=min(cnt[1],cnt[2]);
ans+=min(cnt[1],cnt[2])+cnt[0];
cnt[1]-=tmp;
cnt[2]-=tmp;
ans+=cnt[1]/3+cnt[2]/3;
printf("%d\n",ans);
}
return 0;
}
C - Lose it!
贪心就行......就像拦截导弹第二问那样......
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
int n;
const int N=500050;
int a[N];
int num[]={0,4,8,15,16,23,42};
queue <int> q[10];
int ans;
bool Exit(int i,int j)
{
while(q[i].front()>q[j].front()&&!q[j].empty())q[j].pop();
return q[j].empty();
}
int main()
{
cin>>n;
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
for(int i=1;i<=n;++i)
{
for(int j=1;j<=6;++j)
if(a[i]==num[j])q[j].push(i);
}
while(true)
{
if(Exit(1,2))break;
if(Exit(2,3))break;
if(Exit(3,4))break;
if(Exit(4,5))break;
if(Exit(5,6))break;
ans++;
for(int i=1;i<=6;++i)q[i].pop();
}
printf("%d\n",n-ans*6);
return 0;
}
D - Recover it!
这题题意还看了半天......愣是没理解append啥意思
我们把b从大到小排序，发现只需要扫一遍就行。
一个数无非就两种情况：是质数和不是质数。
是质数的话说明肯定是由一个更小的质数生成而来，更小的那个质数就在后面，并且是a中的数；
不是质数的话这个数就肯定是a中的数，并且生成了一个更小的数。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
const int N=300050;
int n;
int b[N<<1];
bool vis[N*20];
int cnt[N*20];
int pri[N];
int no[N*20],tot;
vector <int> a;
bool cmp(const int &x,const int &y){return x>y;}
bool isprime(int x)
{
for(int i=2;i<=sqrt(x);++i)if(x%i==0)return false;
return true;
}
void init()
{
for(int i=2;i<=3000000;++i)
{
if(!vis[i]){pri[++tot]=i;no[i]=tot;}
for(int j=1;j<=tot&&i*pri[j]<=3000000;++j)
{
vis[i*pri[j]]=1;
if(i%pri[j]==0)break;
}
}
}
int main()
{
init();
cin>>n;
for(int i=1;i<=n*2;++i)scanf("%d",&b[i]),cnt[b[i]]++;
sort(b+1,b+2*n+1,cmp);
for(int i=1;i<=n*2;++i)
{
if(cnt[b[i]]==0)continue;
if(isprime(b[i]))
{
cnt[b[i]]--;
cnt[no[b[i]]]--;
a.push_back(no[b[i]]);
}
else
{
int num=0;
for(int j=2;j<=sqrt(b[i]);++j)
{
if(b[i]%j==0){num=b[i]/j;break;}
}
a.push_back(b[i]);
cnt[num]--;
cnt[b[i]]--;
}
}
for(int i=0;i<a.size();++i)printf("%d ",a[i]);
puts("");
return 0;
}
E - Cover it!
对整张图黑白染色就行......
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
const int N=200050;
int n,m;
struct edge
{
int v,nxt;
}e[N<<1];
int head[N],ecnt;
inline void ad(int u,int v)
{
e[++ecnt].v=v;e[ecnt].nxt=head[u];head[u]=ecnt;
}
int c[N];
bool vis[N];
int cnt1,cnt2;
void dfs(int u,int fa)
{
if(vis[u])return;
vis[u]=1;
if(!c[fa])c[u]=1;
else if(c[fa]==1)c[u]=2;
else if(c[fa]==2)c[u]=1;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa)continue;
dfs(v,u);
}
}
int main()
{
int Test;cin>>Test;
while(Test--)
{
scanf("%d%d",&n,&m);
cnt1=cnt2=0;
memset(head,0,(n+5)*sizeof(int));
memset(vis,0,(n+5)*sizeof(int));
memset(e,0,(m*2+5)*sizeof(int));
memset(c,0,(n+5)*sizeof(int));
for(int i=1;i<=m;++i)
{
int x,y;
scanf("%d%d",&x,&y);
ad(x,y),ad(y,x);
}
c[1]=1;
dfs(1,1);
for(int i=1;i<=n;++i)
{
if(c[i]==1)cnt1++;
else cnt2++;
}
if(cnt1<=cnt2)
{
printf("%d\n",cnt1);
for(int i=1;i<=n;++i)
{
if(c[i]==1)printf("%d ",i);
}
}
else
{
printf("%d\n",cnt2);
for(int i=1;i<=n;++i)
{
if(c[i]==2)printf("%d ",i);
}
}
puts("");
}
return 0;
}
F - Destroy it!
一道还算不错的dp题。
首先，对于每一轮，我们可以只选择其中五张牌：花费为1的伤害最高的3张，花费为2伤害最高的1张，花费为三伤害最高的1张。为什么呢？因为限定每一轮花费不超过3，所以组合一下发现花费为1的最多用三张，其他同理。
然后因为还有一个双倍伤害的设定，那么dp数组需要再开一维表示现在是用到的第几张牌。
然后决策最多有6种：对用一张、两张、三张讨论可得6种决策。
然后就可以上dp了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
struct node
{
int c1,c2,c3;
ll x1[4],x2,x3;
}a[N];
bool cmp(ll x,ll y)
{
return x>y;
}
ll dp[10],temp[10];
int main()
{
int T;
scanf("%d",&T);
int n;
int t=1;
while(T--)
{
scanf("%d",&n);
vector<ll>tmp;
tmp.clear();
for(int i=1;i<=n;i++)
{
ll c,d;
scanf("%lld%lld",&c,&d);
if(c==1)
{
tmp.push_back(d);
a[t].c1++;
}
else if(c==2)
{
a[t].c2++;
a[t].x2=max(a[t].x2,d);
}
else
{
a[t].c3++;
a[t].x3=max(a[t].x3,d);
}
}
sort(tmp.begin(),tmp.end(),cmp);
for(int i=0;i<3&&i<a[t].c1;i++)
{
//cout<<tmp[i]<<endl;
a[t].x1[i+1]=tmp[i];
}
t++;
}
memset(dp,-1,sizeof dp);
dp[0]=0;
//cout<<t<<endl;
for(int i=1;i<t;i++)
{
ll *x1=a[i].x1,x2=a[i].x2,x3=a[i].x3;
//cout<<x1[0]<<endl;
int c1=a[i].c1,c2=a[i].c2,c3=a[i].c3;
memcpy(temp,dp,sizeof dp);
for(int j=0;j<10;j++)
{
if(temp[j]==-1)
continue;
//选1张
if(j<9)
{
if(c1)
dp[j+1]=max(dp[j+1],temp[j]+x1[1]);
if(c2)
dp[j+1]=max(dp[j+1],temp[j]+x2);
if(c3)
dp[j+1]=max(dp[j+1],temp[j]+x3);
}
else
{
if(c1)
dp[0]=max(dp[0],temp[j]+2*x1[1]);
if(c2)
dp[0]=max(dp[0],temp[j]+2*x2);
if(c3)
dp[0]=max(dp[0],temp[j]+2*x3);
}
//选2张
if(j<8)
{
if(c1>=2)
dp[j+2]=max(dp[j+2],temp[j]+x1[1]+x1[2]);
if(c2&&c1)
dp[j+2]=max(dp[j+2],temp[j]+x2+x1[1]);
}
else
{
if(c1>=2)
dp[j-8]=max(dp[j-8],temp[j]+2*x1[1]+x1[2]);
if(c2&&c1)
{
ll maxx=max(x2,x1[1]);
dp[j-8]=max(dp[j-8],temp[j]+x2+x1[1]+maxx);
}
}
//选3张
if(j<7)
{
if(c1>=3)
{
dp[j+3]=max(dp[j+3],temp[j]+x1[1]+x1[2]+x1[3]);
}
}
else
{
if(c1>=3)
{
dp[j-7]=max(dp[j-7],temp[j]+x1[1]*2+x1[2]+x1[3]);
}
}
}
}
ll ans=0;
for(int i=0;i<=9;i++)
{
ans=max(ans,dp[i]);
}
printf("%lld\n",ans);
return 0;
}
Comments NOTHING