[ABC192F] Potion
分析
设选择的总和为 \(sum\)。
不难发现：
\(x\%k=sum\%k\)。
又因为：
\(ans=(x-sum)/k\)。
不难发现\(sum\)只与\(\%k\)有关，且当\(k\)一定时，\(sum\)越大，\(ans\)越小。
因为\(k\)的值域很小，显然可以对于每一个\(k\),用01背包求解出\(\%k\)意义下的最大\(sum\)。
计算答案即可。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200;
int dp[N][N][N],n,a[N],x,ans=LLONG_MAX;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>x;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
memset(dp,-63,sizeof(dp));
for(int i=1;i<=n;i++)
{
dp[i][0][0]=0;
for(int j=1;j<=n;j++)
{
for(int k=j;k>=1;k--)
{
for(int w=0;w<i;w++)
{
if(dp[i][k-1][w]<0)
continue;
dp[i][k][(w+a[j])%i]=max(dp[i][k][(w+a[j])%i],dp[i][k-1][w]+a[j]);
}
}
}
if(dp[i][i][x%i]>=0)
ans=min(ans,(x-dp[i][i][x%i])/i);
}
cout<<ans;
return 0;
}
[ABC195E] Lucky 7 Battle
分析
博弈论dp模板题。
观察到数据范围较大，加上记忆化。
复杂度线性。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+100;
int n,f[N][7];
string s1,s2;
bool dfs(int x,int mod)
{
if(x==n&&mod==0)
return true;
else if(x==n)
return false;
if(f[x][mod]!=0)
{
if(f[x][mod]==1)
return true;
else
return false;
}
if(s2[x]=='A')
{
if(dfs(x+1,(mod*10)%7)==false||dfs(x+1,(mod*10+s1[x]-'0')%7)==false)
{
f[x][mod]=2;
return false;
}
else
{
f[x][mod]=1;
return true;
}
}
else
{
if(dfs(x+1,(mod*10)%7)==true||dfs(x+1,(mod*10+s1[x]-'0')%7)==true)
{
f[x][mod]=1;
return true;
}
else
{
f[x][mod]=2;
return false;
}
}
}
int main()
{
cin>>n>>s1>>s2;
if(dfs(0,0)==true)
cout<<"Takahashi";
else
cout<<"Aoki";
return 0;
}
[ABC199E] Permutation
分析
数据范围很小，考虑状压。
优先考虑全排列的朴素求法。
用当前状态为1表示出现在当前前缀，顺序求解。
又因为本题限制很小，可以直接遍历判断。
因此状压得证。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200;
int n,m,x[N],y[N],z[N],dp[1<<20];
int get(int x)
{
int ans=0;
for(int i=0;i<n;i++)
{
if((x&(1<<i))!=0)
ans++;
}
return ans;
}
bool check(int x,int v,int w)
{
for(int i=0;i<v;i++)
{
if((x&(1<<i))!=0)
w--;
}
if(w<0)
return false;
else
return true;
}
void solve(int x)
{
for(int i=0;i<n;i++)
{
if((x&(1<<i))!=0)
{
dp[x]+=dp[x^(1<<i)];
}
}
return;
}
signed main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>x[i]>>y[i]>>z[i];
}
dp[0]=1;
for(int i=1;i<(1<<n);i++)
{
int num=get(i);
bool fl=0;
for(int j=1;j<=m;j++)
{
if(x[j]==num)
{
if(check(i,y[j],z[j])==false)
{
fl=1;
break;
}
}
}
if(fl==1)
continue;
solve(i);
}
cout<<dp[(1<<n)-1];
return 0;
}
[ABC191F] GCD or MIN
分析
观察到GCD和MIN都让答案变小，因此答案应该不大于给定数的最小值。
我们考虑MIN并不会改变现有的数，所以我们只要看GCD够得到哪些数就可以。
我们拆出所有因数，然后选不大于给定数最小值的部分。
对于一个因数，我们判断他能不能被取到：
我们找到所有含有他的数，取他们的GCD，相同就贡献+1。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e3+100;
int n,a[N],l,minn=INT_MAX,ans,maxs=INT_MIN;
vector<int>p;
map<int,vector<int>>mp;
bool check(int x)
{
int s=mp[x][0];
for(int i=1;i<mp[x].size();i++)
{
s=__gcd(s,mp[x][i]);
}
if(s==x)
return true;
else
return false;
}
void pre()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=sqrt(a[i]);j++)
{
if(a[i]%j==0)
{
if(j<=minn)
{
p.push_back(j);
mp[j].push_back(a[i]);
}
if(a[i]/j<=minn)
{
p.push_back(a[i]/j);
mp[a[i]/j].push_back(a[i]);
}
}
}
}
sort(p.begin(),p.end());
l=unique(p.begin(),p.end())-p.begin()-1;
return ;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
minn=min(minn,a[i]);
maxs=max(maxs,a[i]);
}
pre();
for(int i=0;i<=l;i++)
{
if(check(p[i])==true)
ans++;
}
cout<<ans;
return 0;
}