T1
读入字符串，替换''即可，其他按原样输出
参考代码
#include
using namespace std;
string a;
int main()
{
getline(cin,a);
for(int i=0;i<a.length();i++)
{
if(a[i]=='<') cout<<"<";
else if(a[i]=='>') cout<<">";
else cout<<a[i];
}
return 0;
}T2
简化题意：
n个数相乘得到数g，求g二进制下后导0的个数
考虑把n个数都换成二进制，模拟二进制相乘即可发现规律
答案即是n个数的二进制下后导0的个数相加
证明
我们假设2个数相乘，分别是20，22
首先将他们2个转为二进制
- 20：10100
- 22：10110
我们再模拟二进制下的相乘
可以发现得出的数的二进制下后导0即是相乘的两个数的二进制下后导0数量之和
参考代码
#include
using namespace std;
int n,x,ans;
int main()
{
cin>>n;
while(n--){
scanf("%d",&x);
while(x) (x&1)?x=0:ans++,x>>=1;
}
cout<<ans<<"\n";
return 0;
}T3
前置知识
杨辉三角形与组合数的关系
线性求逆元
分析
杨辉三角形的第n行的m个数可表示为 C(n-1，m-1)，即为从n-1个不同元素中取m-1个元素的组合数。
其实就是先预处理（预处理阶乘和逆元的阶乘），然后O（1）求组合数再乘起来取模即可参考代码
#include using namespace std; const int N=1e6+1,mod=1e9+7; unsigned int C[N],g[N]; int main(){ int n,ans=1; scanf("%d",&n); C[0]=g[0]=g[1]=1; for(int i=2;i<n/2+1;++i)g[i]=(1ULL*g[mod%i]*(mod-mod/i))%mod; for(int i=1;i<=n/2+1;++i)C[i]=(1ULL*((1ULL*C[i-1]*(n-i))%mod)*g[i])%mod; for(unsigned int i=1;i<=n/2;++i)ans=(1ULL*ans*C[i-1])%mod; ans=1ULL*ans*ans%mod; if(n&1) ans=1ULL*ans*C[n/2]%mod; printf("%d",ans); return 0; }T4
哈夫曼树模板题
特判一下只有一种字母的情况（虽然测试数据并没有这种情况QWQ）
参考代码
#include
using namespace std;
string a;
int ans,t[200];
priority_queue v;
signed main()
{
cin>>a;
for(int i=0;i<a.length();i++) t[a[i]]++;
for(int i='a';i<='z';i++) if(t[i]) v.push(-t[i]);
if(v.size()==1)
return printf("%d\n",a.length())&0;
while(v.size()!=1){
int k=0;
k+=v.top();v.pop();
k+=v.top();v.pop();
v.push(k);ans+=k;
}
cout<<-ans<<"\n";
return 0;
}T5
前置知识：
- 勾股定理
- 海伦公式
- 空间向量
- 三棱锥体积公式
推理
我们知道四面体即是三棱锥
通过 底高即可得到体积
我们用前3个点构成的面当作底面
用海伦公式求底面积，调用
用空间向量求高，首先求出底面的法向量，在底面上随便找一个点连向第4个点构成向量，求此向量在法向量上的投影即是高
参考代码
#include
using namespace std;
struct Vector{
int x[5];
}t[10],a,b,c,d;
double h;
int main()
{
for(int i=0;i<4;i++)
for(int j=0;j<3;j++)
cin>>t[i].x[j];
for(int i=0;i<3;i++){
a.x[i]=t[1].x[i]-t[0].x[i];
b.x[i]=t[2].x[i]-t[0].x[i];
d.x[i]=t[3].x[i]-t[0].x[i];
}
for(int i=0;i<3;i++)
c.x[i]=a.x[(i+1)%3]*b.x[(i+2)%3]-b.x[(i+1)%3]*a.x[(i+2)%3];
int cd=0;
for(int i=0;i<3;i++)
cd+=c.x[i]*d.x[i];
h=fabs(cd/sqrt(c.x[0]*c.x[0]+c.x[1]*c.x[1]+c.x[2]*c.x[2]));
double k[4],p,s;
for(int i=0;i<3;i++)
k[i]=sqrt((t[i].x[0]-t[(i+1)%3].x[0])*(t[i].x[0]-t[(i+1)%3].x[0])+(t[i].x[1]-t[(i+1)%3].x[1])*(t[i].x[1]-t[(i+1)%3].x[1])+(t[i].x[2]-t[(i+1)%3].x[2])*(t[i].x[2]-t[(i+1)%3].x[2]));
p=(k[0]+k[1]+k[2])/2;
s=sqrt(p*(p-k[0])*(p-k[1])*(p-k[2]));
printf("%.1lf\n",s*h/3);
cout<<s<<"\n";
cout<<h<<"\n";
return 0;
}T6
先求一遍前缀和数组为h
需要求满足 &&
的式子
题目就转为求前缀和数组中逆序对的数目
使用归并排序求逆序对
或使用高级数据结构维护（如平衡树）
参考代码（归并排序）
#include
using namespace std;
long long n;
long long h[1000008];
long long a[1000008];
long long c[1000008];
long long ans;
void fsort(long long l,long long r)
{
if(l>=r) return ;
long long tot=0;
long long mid=(l+r)/2;
long long aa=l,bb=mid+1;
fsort(l,mid);
fsort(mid+1,r);
while(aa<=mid&&bb<=r){
if(a[aa]<a[bb]){
c[++tot]=a[aa++];
ans+=(r-bb+1);
}
else{
c[++tot]=a[bb++];
}
}
while(aa<=mid)
c[++tot]=a[aa++];
while(bb<=r)
c[++tot]=a[bb++];
for(long long i=l,j=1;i<=r;i++,j++)
a[i]=c[j];
}
int main()
{
scanf("%lld",&n);
a[1]=h[1]=0;
n++;
for(long long i=2;i<=n;i++){
scanf("%lld",&h[i]);
a[i]=a[i-1]+h[i];
}
fsort(1,n);
cout<<ans<<"\n";
return 0;
}参考代码（Splay树）
#include
#define ll long long
#define int long long
#define inf INT_MAX
#define lc(x) s[x].ch[0]
#define rc(x) s[x].ch[1]
using namespace std;
const int N=1e6+10;
int n,rt,tot;
int a[N];
struct nkl {
int ch[2],siz,cnt,val,fa;
} s[N];
inline int ident(int x,int y) {
return (rc(y)==x);
}
inline void cn(int x,int y,int k) {
s[x].fa=y;
s[y].ch[k]=x;
}
inline void upd(int x) {
s[x].siz=s[lc(x)].siz+s[rc(x)].siz+s[lc(x)].cnt+s[rc(x)].cnt;
}
inline void rotate(int x) {
int y=s[x].fa,z=s[y].fa,k=ident(x,y);
cn(s[x].ch[k^1],y,k);
cn(x,z,ident(y,z));
cn(y,x,k^1);
upd(y),upd(x);
}
inline void splay(int x,int to) {
if(!to) rt=x;
while(s[x].fa!=to) {
int y=s[x].fa,z=s[y].fa;
if(z!=to)
ident(x,y)^ident(y,z) ? rotate(x):rotate(y);
rotate(x);
}
}
inline void newcode(int &now,int x,int fa) {
now=++tot;
s[now].val=x;
s[now].fa=fa;
s[now].cnt++;
}
inline void ins(int &now,int x,int fa) {
if(!now) newcode(now,x,fa),splay(now,0);
else if(s[now].val<x) ins(s[now].ch[1],x,now);
else if(s[now].val>x) ins(s[now].ch[0],x,now);
else s[now].cnt++,splay(now,0);
}
signed main() {
scanf("%lld",&n);
for (int i=1; i<=n; i++)
scanf("%lld",&a[i]),a[i]+=a[i-1];
ll ans=0;
for (int i=1; i<=n; i++) {
ins(rt,a[i],0);
ans+=s[lc(rt)].siz+s[lc(rt)].cnt;
if(a[i]>0) ans++;
}
printf("%lld\n",ans);
return 0;
}T7
题目灵感来自现实，首先某OJ相信大家都看出来是哪个网站了，实际上它真的做了这个非常奇怪的js校验。当然这个校验的反爬虫能力其实并不强，你只需要在爬虫里面去计算这个hash值就行了。（我猜测它并不是真的为了防止爬虫，而是避免直接用Python利用Requests库短时间发送大量请求，这样的话你至少需要计算hash来拖时间）这道题的数据范围就是真实的数据范围，所以算法很有趣对吧，说不定就用上了。
题解
题意是让你去算一个字符串的反哈希，哈希的取值范围是[0,1008]。注意到取值范围很小，所以可以通过大量随机撞库获取到一个字符串到哈希值的映射表（被称为彩虹表）的东西，然后直接查询就可以了。
T8
题目灵感来自现实，首先某OJ相信大家都看出来是哪个网站了，实际上它真的做了这个非常奇怪的隐藏表单。当然这个隐藏的反爬虫能力其实并不强，你只需要在爬虫里面去获取这个隐藏表单值就行了。这道题的数据是真实的数据上稍加改动，所以算法很有趣对吧，说不定就用上了。
题解
题意是让你去找一个字符串，抓住字符串特征，字符串匹配即可
T9
模拟即可
参考代码
#include
using namespace std;
string t;
int a[105];
int tot;
queue v[4];
string cname[3]={"xiran","sanqiu"};
string pai[24]={"","A","2","3","4","5","6","7","8","9","10","J","Q","K"};
stack q;
bool flag[21];
void get(int k,int x)
{
int all=2;
while(q.size()&&all){
v[x].push(q.top());
flag[q.top()]=0;
if(q.top()==k)
all--;
q.pop();
}
}
void work(int x)
{
int k=v[x].front();
v[x].pop();
q.push(k);
if(k==11){
if(q.size()==1)
return;
else{
get(0,x);
work(x);
}
}
else{
if(flag[k]){
get(k,x);
work(x);
}
else
flag[k]=1;
}
}
int main()
{
cin>>t;
for(int i=0;i<=t.size();i++){
if(t[i]=='A') a[++tot]=1;
else if(t[i]>='2'&&t[i]<='9') a[++tot]=t[i]-'0';
else if(t[i]=='1') {a[++tot]=10;i++;}
else if(t[i]=='J') a[++tot]=11;
else if(t[i]=='Q') a[++tot]=12;
else if(t[i]=='K') a[++tot]=13;
}
for(int i=1;i<=tot;i++) v[i&1].push(a[i]);
int win=0;
while(1){
work(1);
if(v[1].size()==0) {win=0;break;}//判断游戏是否结束
work(0);
if(v[0].size()==0) {win=1;break;}//判断游戏是否结束
}
cout<<cname[win]<<"\n";
while(v[win].size()){
cout<<pai[v[win].front()]<<" ";
v[win].pop();
}
return 0;
}T10
证明
我们先定义2个集合
- 集合A 代表溪染拥有的所有优惠券的集合
- 集合B 为集合A的子集
如果我们使用集合B里面的优惠券，无论我们如何顺序使用（前提是所有优惠券能够使用）
集合B带来的优惠总额是不变的，考虑以不同的顺序使用，会对什么造成影响？
再定义
- 排列P 为集合B里优惠券的某种排列
- 金钱K 为若按照排列P使用优惠券，保证所有优惠券可以使用的情况下，商品最初最少为多少元
按照排列P，优惠券的参数
我们来看一看金钱K需要满足什么式子，如下：
- ......
再定义
- 最优排列 对于一个集合B有很多排列P，当某一个排列P的金钱K最小时，我们称其为最优排列
不难证明对于最优答案的合法排列总有一个是最优排列（证明略）
现在问题转为如何求集合B的最优排列
可以证明，当按照下列式子排序后，得到的就是最优排序
证明可以参考 [NOIP2012 提高组] 国王游戏 的证明方法
不难证明集合B的最优排列是集合A的最优排列的子序列（证明略）
那么这道题就十分明了了，我们先计算出集合A的最优排列
再考虑选取集合B，由于我们已经得到了最优排序
我们就不必再考虑使用顺序的问题（按照最优排序使用即可）
此时问题已经变成了01背包问题，按照规则构建01背包DP方程即可， 表示购买价格为i的商品最少需要多少钱
注意，01背包枚举优惠券的顺序需要按照顺序枚举！
DP枚举时，先枚举的是最后选的，所以按照集合A的最优排列的倒序枚举
至此，此题完
参考代码
#include
#define N 100005
using namespace std;
int n,k;
struct oppo{
int a,b;
}t[N];
bool rule(oppo a,oppo b){
return a.a-a.b>b.a-b.b;
}
int dp[1000005];
int main()
{
cin>>n>>k;
for(int i=1;i<=k;i++) dp[i]=i;
for(int i=1;i<=n;i++)
scanf("%d%d",&t[i].a,&t[i].b);
sort(t+1,t+n+1,rule);
for(int i=n;i>=1;i--)
for(int j=k;j>=t[i].a;j--)
dp[j]=min(dp[j],dp[j-t[i].b]);
cout<<dp[k]<<"\n";
return 0;
}
京公网安备 11010502036488号