K题
https://ac.nowcoder.com/acm/contest/32708/K
题意
给定一个场数A，给定一个比例a/b 从0开始，每当胜率小于等于a/b，这场必赢，否则必输，问n场中能赢多少场、
分析
这道题是一个贪心题，首先除了最后一场之外其他时间一定符合x/n<=a/b，但是我们要赢的尽可能多所以最后一场最好赢了之后超过a/b，因此x=a*(n-1)/b+1
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
typedef long long ll;
ll mod=1e18+7;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
ll n,a,b;
scanf("%lld%lld%lld",&n,&a,&b);
ll x=a*(n-1)/b+1;
x=max(x,1ll);
cout<<x<<endl;
}
}
D题
https://ac.nowcoder.com/acm/contest/32708/D
题意
规定一种完美分配方法，把一个序列分成A，B两个序列，A序列不下降，B序列不上升，AB可以为空，数字要按在原序列的顺序插入
分析
这道题是一个构造题，首先全是1一共有k=2^n，那么在这个基础上加上更大的数k还会增加2^n-1个(想到了前一半之后这个没有想到)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
typedef long long ll;
typedef pair<int, int> pii;
vector<pii>ve;
vector<int>a;
vector<int>ans;
int main()
{
int k;
scanf("%d",&k);
if(k==0) printf("4\n3 4 1 2");
else if(k==1) printf("6\n1 1 4 5 1 4");
else
{
ll z=2;
for(int i=1;;i++)
{
a.push_back(z-1);
z*=2;
if(z>=1e9) break;
}
z=2;
for(int i=1;;i++)
{
if(z*2>k)
{
ve.push_back({1,i});
k-=z;
break;
}
z*=2;
}
int cnt=2;
int zz=1;
//cout<<k<<endl;
while(k)
{
int z=upper_bound(a.begin(),a.end(),k)-a.begin();
//cout<<k<<" "<<a[z]<<endl;
//cout<<z<<" "<<a[z-1]<<endl;
ve.push_back({cnt++,z});
k-=a[z-1];
}
int res=0;
for(auto [k,v]:ve)
{
res+=v;
for(int i=1;i<=v;i++) ans.push_back(k);
}
cout<<res<<endl;
for(int i=0;i<ans.size();i++) cout<<ans[i]<<" ";
}
}
F题
https://ac.nowcoder.com/acm/contest/32708/F
题意
规定一种完美分配方法，把一个序列分成A，B两个序列，A序列不下降，B序列不上升，AB可以为空，数字要按在原序列的顺序插入
分析
这题是一个数学题+树形dp题，首先我们要处理这个公式，最后推的v个b的权值嗯平均值最大即为答案，然后用树形dp求解，(这里需要推出答案一定是两个数或者三个数相加得到的)
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int h[N],ne[N],e[N],w[N],idx;
int dp[N][2];
double res=-1e8;
void add(int a, int b) // 添加一条边a->b
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void dfs(int u,int fa)
{
dp[u][0]=dp[u][1]=-1e8;
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(j==fa) continue;
dfs(j,u);
if(w[j]>=dp[u][0])
{
dp[u][1]=dp[u][0];
dp[u][0]=w[j];
}
else if(w[j]>dp[u][1]) dp[u][1]=w[j];
}
res=max(res,((double)w[u]+dp[u][0])/2);
res=max(res,((double)w[u]+dp[u][0]+dp[u][1])/3);
}
int main()
{
int n;
cin>>n;
memset(h, -1, sizeof h);
for(int i=1;i<=n;i++) cin>>w[i];
for(int i=1;i<n;i++)
{
int a,b;
cin>>a>>b;
add(a,b);add(b,a);
}
dfs(1,-1);
for(int i=1;i<=n;i++) w[i]=-w[i];
dfs(1,-1);
printf("%.6lf",res*res/4);
}
A题
https://ac.nowcoder.com/acm/contest/32708/A
题意
大模拟
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
typedef long long ll;
char Ala[][20] = {
" H H O ",
" | | || ",
"H-N-C-C-O-H",
" | ",
" H-C-H ",
" | ",
" H ",
" ",
" ",
" ",
" ",
" ",
" ",
" "
};
char Asp[][20] = {
" H H O ",
" | | || ",
"H-N-C-C-O-H",
" | ",
" H-C-H ",
" | ",
" O=C-O-H ",
" ",
" ",
" ",
" ",
" ",
" ",
" "
};
char Asn[][20] = {
" H H O ",
" | | || ",
"H-N-C-C-O-H",
" | ",
" H-C-H ",
" | ",
" O=C-N-H ",
" | ",
" H ",
" ",
" ",
" ",
" ",
" "
};
char Cys[][20] = {
" H H O ",
" | | || ",
"H-N-C-C-O-H",
" | ",
" H-C-S-H ",
" | ",
" H ",
" ",
" ",
" ",
" ",
" ",
" ",
" "
};
char Gly[][20] = {
" H H O ",
" | | || ",
"H-N-C-C-O-H",
" | ",
" H ",
" ",
" ",
" ",
" ",
" ",
" ",
" ",
" ",
" "
};
char Ser[][20] = {
" H H O ",
" | | || ",
"H-N-C-C-O-H",
" | ",
" H-C-O-H ",
" | ",
" H ",
" ",
" ",
" ",
" ",
" ",
" ",
" "
};
char Met[][20] = {
" H H O ",
" | | || ",
"H-N-C-C-O-H",
" | ",
" H-C-H ",
" | ",
" H-C-H ",
" | ",
" S ",
" | ",
" H-C-H ",
" | ",
" H ",
" "
};
char Thr[][20] = {
" H H O ",
" | | || ",
"H-N-C-C-O-H",
" | ",
" H-C-O-H ",
" | ",
" H-C-H ",
" | ",
" H ",
" ",
" ",
" ",
" ",
" "
};
char Gln[][20] = {
" H H O ",
" | | || ",
"H-N-C-C-O-H",
" | ",
" H-C-H ",
" | ",
" H-C-H ",
" | ",
" O=C-N-H ",
" | ",
" H ",
" ",
" ",
" "
};
char Glu[][20] = {
" H H O ",
" | | || ",
"H-N-C-C-O-H",
" | ",
" H-C-H ",
" | ",
" H-C-H ",
" | ",
" O=C-O-H ",
" ",
" ",
" ",
" ",
" "
};
char P[][20] = {
" O H",
" || |",
"-C---N-",
" "
};
int n,m;
vector<int>ve;
vector<int>va;
map<string,int>ma;
map<int,int>mc;
map<int,int>mb;
int ans;
void init()
{
ma["Ala"]=1;
ma["Asn"]=2;
ma["Asp"]=3;
ma["Cys"]=4;
ma["Gln"]=5;
ma["Glu"]=6;
ma["Gly"]=7;
ma["Met"]=8;
ma["Ser"]=9;
ma["Thr"]=10;
mb[1]=89;
mb[2]=132;
mb[3]=133;
mb[4]=121;
mb[5]=146;
mb[6]=147;
mb[7]=75;
mb[8]=149;
mb[9]=105;
mb[10]=119;
mc[1]=7;
mc[2]=9;
mc[3]=7;
mc[4]=7;
mc[5]=11;
mc[6]=9;
mc[7]=5;
mc[8]=13;
mc[9]=7;
mc[10]=9;
}
void dfs_u(int u,int w)
{
if(u>=2)
{
//for(int i=0;i<va.size();i++) cout<<va[i];
//cout<<endl;
int cc=0;
for(int j=0;j<va.size();j++)
{
cc=max(cc,mc[va[j]]);
}
for(int i=0;i<=cc;i++)
{
bool flag=0;
if(i==2)
{
for(int j=0;j<va.size();j++)
{
if(j==0)
{
for(int k=0;k<=7;k++)
{
if(va[j]==1) cout<<Ala[i][k];
if(va[j]==2) cout<<Asn[i][k];
if(va[j]==3) cout<<Asp[i][k];
if(va[j]==4) cout<<Cys[i][k];
if(va[j]==5) cout<<Gln[i][k];
if(va[j]==6) cout<<Glu[i][k];
if(va[j]==7) cout<<Gly[i][k];
if(va[j]==8) cout<<Met[i][k];
if(va[j]==9) cout<<Ser[i][k];
if(va[j]==10) cout<<Thr[i][k];
}
cout<<"--";
}
else if(j==va.size()-1)
{
for(int k=2;k<=10;k++)
{
if(va[j]==1) cout<<Ala[i][k];
if(va[j]==2) cout<<Asn[i][k];
if(va[j]==3) cout<<Asp[i][k];
if(va[j]==4) cout<<Cys[i][k];
if(va[j]==5) cout<<Gln[i][k];
if(va[j]==6) cout<<Glu[i][k];
if(va[j]==7) cout<<Gly[i][k];
if(va[j]==8) cout<<Met[i][k];
if(va[j]==9) cout<<Ser[i][k];
if(va[j]==10) cout<<Thr[i][k];
}
}
else
{
for(int k=2;k<=7;k++)
{
if(va[j]==1) cout<<Ala[i][k];
if(va[j]==2) cout<<Asn[i][k];
if(va[j]==3) cout<<Asp[i][k];
if(va[j]==4) cout<<Cys[i][k];
if(va[j]==5) cout<<Gln[i][k];
if(va[j]==6) cout<<Glu[i][k];
if(va[j]==7) cout<<Gly[i][k];
if(va[j]==8) cout<<Met[i][k];
if(va[j]==9) cout<<Ser[i][k];
if(va[j]==10) cout<<Thr[i][k];
}
cout<<"--";
}
}
}
else
{
for(int j=0;j<va.size();j++)
{
if(j==0)
{
for(int k=0;k<=9;k++)
{
if(va[j]==1) cout<<Ala[i][k];
if(va[j]==2) cout<<Asn[i][k];
if(va[j]==3) cout<<Asp[i][k];
if(va[j]==4) cout<<Cys[i][k];
if(va[j]==5) cout<<Gln[i][k];
if(va[j]==6) cout<<Glu[i][k];
if(va[j]==7) cout<<Gly[i][k];
if(va[j]==8) cout<<Met[i][k];
if(va[j]==9) cout<<Ser[i][k];
if(va[j]==10) cout<<Thr[i][k];
}
}
else
{
for(int k=2;k<=9;k++)
{
if(va[j]==1) cout<<Ala[i][k];
if(va[j]==2) cout<<Asn[i][k];
if(va[j]==3) cout<<Asp[i][k];
if(va[j]==4) cout<<Cys[i][k];
if(va[j]==5) cout<<Gln[i][k];
if(va[j]==6) cout<<Glu[i][k];
if(va[j]==7) cout<<Gly[i][k];
if(va[j]==8) cout<<Met[i][k];
if(va[j]==9) cout<<Ser[i][k];
if(va[j]==10) cout<<Thr[i][k];
}
}
}
}
cout<<endl;
}
}
w-=18;
for(int i=0;i<ve.size();i++)
{
w+=mb[ve[i]];
va.push_back(ve[i]);
if(w<=m) dfs_u(u+1,w);
va.pop_back();
w-=mb[ve[i]];
}
}
void dfs(int u,int w)
{
if(u>=2) ans++;
int c=w-18;
for(int i=0;i<ve.size();i++)
{
c+=mb[ve[i]];
if(c<=m) dfs(u+1,c);
c-=mb[ve[i]];
}
}
int main()
{
//ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
init();
string s;
for(int i=1;i<=n;i++)
{
cin>>s;
ve.push_back(ma[s]);
}
sort(ve.begin(),ve.end());
ve.erase(unique(ve.begin(),ve.end()),ve.end());
//for(int i=0;i<ve.size();i++) cout<<ve[i]<<" ";
//cout<<endl;
dfs(0,18);
cout<<ans<<endl;
dfs_u(0,18);
}
