B

#include<bits/stdc++.h>
using namespace std;
const int MAXN=8005;
int n,q;
int t[MAXN];//原来在位置x的数 现在在t[x]
struct node
{
int val,num;
//val存储元素的值 num存储排序之前元素的位置
} a[MAXN];
bool cmp(node x,node y)
{
//自定义比较元素大小的方式 若x<y 输出1 否则输出0
//在此题中相同的两个元素排序后相对位置不能改变
if(x.val==y.val) return x.num<y.num;//编号更小的排序后一定在前面
else return x.val<y.val;
}
int main(){
freopen("sort.in","r",stdin);
freopen("sort.out","w",stdout);
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i].val);
a[i].num=i;
}
sort(a+1,a+n+1,cmp);//排序
for(int i=1;i<=n;i++) t[a[i].num]=i;//以前在数组中位于num的元素现在位于i
for(int i=1;i<=q;i++)
{
int opt,x,v;
scanf("%d",&opt);
if(opt==1)
{//单点修改
scanf("%d%d",&x,&v);//Ax->v
a[t[x]].val=v;//以前在数组中位于x的元素现在位于t[x]
//改变了元素大小后 需要重新对数组排序 但是只需对这一个元素进行冒泡
//可能向前冒泡 也可能向后冒泡 所以需要用两个循环
for(int j=n;j>=2;j--)//从后往前进行一遍冒泡排序
{
if(cmp(a[j],a[j-1]))//若a[j]应该排在前面 交换位置
{
node tmp=a[j];
a[j]=a[j-1];
a[j-1]=tmp;
}
}
for(int j=1;j<=n-1;j++)//从前往后进行一遍冒泡排序
{
if(cmp(a[j+1],a[j]))//若a[j+1]应该排在前面 交换位置
{
node tmp=a[j];
a[j]=a[j+1];
a[j+1]=tmp;
}
}
for(int i=1;i<=n;i++) t[a[i].num]=i;//更新对应关系
}
else
{
scanf("%d",&x);
printf("%d\n",t[x]);
}
}
return 0;
}

C

#include<bits/stdc++.h>
using namespace std;
int main()
{
freopen("vigenere.in","r",stdin);
freopen("vigenere.out","w",stdout);
string K,C;//密钥，密文
cin>>K>>C;
int lk=K.size(),lc=C.size();
for(int i=0;i<lc;i++)//现在要求第几个明文
{
int a,b,c;//明文为a 密钥为b 密文为c
char kk=K[i%lk];//取出此时要用的密钥的对应字母 如果长度大于lk 需要取模
if(kk>='A'&&kk<='Z') b=kk-'A'+1;//算当前密钥的这个字母是字母表中第几个
else b=kk-'a'+1;
char cc=C[i];//取出此时密文的对应字母
bool flag=0;//0表示输出小写 1表示输出大写
if(cc>='A'&&cc<='Z')
{
c=cc-'A'+1;
flag=1;
}
else c=cc-'a'+1;
if(c-b<0) a=c-b+26+1;//注意<0时要+26
else a=c-b+1;
if(!flag) printf("%c",a+'a'-1);//根据flag的值来确定输出的大小写
else printf("%c",a+'A'-1);
}
return 0;
}
/*
观察可知，若明文为a，密钥为b，则查表得到的密文c=a+b-1
如明文为'c'，即字母表中第3个数字；密钥为'd'，即字母表中第4个数字
则密文为字母表中第3+4-1=6个数字，即'f'
反之，现在已知密文和密钥，明文为a=c-b+1
为防止出现负数，若c-b<0，需要加上26
*/

D

#include<bits/stdc++.h>
#define INF 200010
using namespace std;
int n;
set<int>s1,s2;//把下标扔在两个set里
int main()
{
freopen("fruit.in","r",stdin);
freopen("fruit.out","w",stdout);
scanf("%d",&n);
int q;
for(int i=1;i<=n;++i)
{
scanf("%d",&q);
if (q) s1.insert(i); //如果是苹果 把下标放在s1中
else s2.insert(i); // 如果是桔子 把下标放在s2中
}
s1.insert(INF);//这里塞INF的原因是防止set空后的出错
s2.insert(INF);
//比如这里找p的时候 如果某个set中没有值 就不能取*s.begin() 会报错
int p;//p里存储我们当前要取苹果还是桔子
if(*s1.begin()<*s2.begin()) p=1; //如果苹果的下标更小 取苹果
else p=0;
int nw=0;//表示我们上一个取的水果下标是多少
while(s1.size()>1 || s2.size()>1)
//需要保证取苹果时 s1中有值 取桔子时 s2中有值
{
if(p==1)//取苹果
{
nw=*s1.upper_bound(nw);//找第一个>nw的元素
//upper_bound 第一个大于的元素
//lower_bound 第一个大于等于的元素
if(nw==INF)//如果没找到 只找到了INF 证明没有可以用的苹果了
{
//重置p和nw
if(*s1.begin()<*s2.begin()) p=1;
else p=0;
nw=0;
printf("\n");//一次取完了 要输出换行
}
else //找到了
{
printf("%d ",nw);//取了，输出，删除
s1.erase(nw);
p=0;//下一次该取桔子
}
}
else //取桔子
{
nw=*s2.upper_bound(nw);//找第一个>nw的元素
if(nw==INF)//如果没找到 只找到了INF 证明没有可以用的桔子了
{
//重置p和nw
if(*s1.begin()<*s2.begin()) p=1;
else p=0;
nw=0;
cout<<endl;//一次取完了 要输出换行
}
else //找到了
{
printf("%d ",nw);//取了，输出，删除
s2.erase(nw);
p=1;//下一次该取苹果
}
}
}
return 0;
}