A. Vitaliy and Pie 从左到右模拟一下
MAXN=200100;;string s;int n;int key[MAXN];int main(){scanf(“%d”,&n);cin>>s;int l=s.length();int cnt=0;for(int i=0;i<l;++i){if(!(i&1)) key[s[i]-‘a’]++;else{if(key[s[i]-‘A’]) key[s[i]-‘A’]–;else cnt++;}}printf(“%d\n”,cnt);return 0;}
B. Pasha and String 题目描述： 给定一个字符串s，然后m个操作，对区间[ai,|s|-ai+1]进行翻转，求最后所得的字符串s’
1.可以用splay，贴个模板就行了 2.用一个rev标记预先记录每个位置翻转的次数，然后从位置i~n/2，对每个位置的rev进行判定，swap(s[i],s[l-i+1])
MAXN=200010;;int n;int sum[MAXN];char s[MAXN];int main(){scanf(“%s”,s);scanf(“%d”,&n);int x;for(int i=1;i<=n;++i){scanf(“%d”,&x);sum[x]^=1;}int l=strlen(s);int flag=0;for(int i=1;i<=l/2;++i){flag^=sum[i];if(flag){swap(s[i-1],s[l-i]);}}cout<<s<<endl;return 0;}
splay：
MAXN=200100;const int INF=1<<30;;int root,tot1,ch[MAXN][2],key[MAXN],pre[MAXN];int s[MAXN],tot2;int rev[MAXN],size[MAXN];int a[MAXN];char str[MAXN];int n,m;void update_rev(int rt){if(!rt) return ;swap(ch[rt][0],ch[rt][1]);rev[rt]^=1;}void push_up(int rt){int lson=ch[rt][0],rson=ch[rt][1];size[rt]=size[lson]+size[rson]+1;}void push_down(int rt){if(rev[rt]){update_rev(ch[rt][0]);update_rev(ch[rt][1]);rev[rt]=0;}}void NewNode(int &rt,int f,int k){if(tot2) rt=s[tot2–];else rt=++tot1;ch[rt][0]=ch[rt][1]=0;pre[rt]=f;key[rt]=k;size[rt]=1;rev[rt]=0;}void build(int &rt,int l,int r,int f){if(l>r) return ;int mid=(l+r)>>1;NewNode(rt,f,str[mid]-‘a’);build(ch[rt][0],l,mid-1,rt);build(ch[rt][1],mid+1,r,rt);push_up(rt);}void init(){root=tot1=tot2=0;rev[root]=ch[root][0]=ch[root][1]=pre[root]=size[root]=0;NewNode(root,0,-1);NewNode(ch[root][1],root,-1);scanf(“%s”,str);n=strlen(str);build(Key_value,0,n-1,ch[root][1]);push_up(ch[root][1]);push_up(root);}void Rotate(int x,int kind){int y=pre[x];push_down(y);push_down(x);ch[y][!kind]=ch[x][kind];pre[ch[x][kind]]=y;if(pre[y])ch[pre[y]][ch[pre[y]][1]==y]=x;pre[x]=pre[y];pre[y]=x;ch[x][kind]=y;push_up(y);}void Splay(int x,int goal){push_down(x);while(pre[x]!=goal) {if(pre[pre[x]]==goal) {Rotate(x,ch[pre[x]][0]==x);} else {int y=pre[x];int kind=ch[pre[y]][0]==y;if(ch[y][kind]==x) {Rotate(x,!kind);Rotate(x,kind);} else {Rotate(y,kind);Rotate(x,kind);}}}push_up(x);if(goal==0) root=x;}int Get_kth(int rt,int k){push_down(rt);int z=size[ch[rt][0]]+1;if(z==k) return rt;if(z>k) return Get_kth(ch[rt][0],k);else return Get_kth(ch[rt][1],k-z);}void Reverse(int x,int y){Splay(Get_kth(root,x),0);Splay(Get_kth(root,y+2),root);update_rev(Key_value);}int cnt;void InOrder(int rt){if(!rt) return ;push_down(rt);InOrder(ch[rt][0]);if(cnt>=1&&cnt<=n){printf(“%c”,key[rt]+’a’);}cnt++;InOrder(ch[rt][1]);}int main(){init();int x;scanf(“%d”,&m);while(m–){scanf(“%d”,&x);Reverse(x,n-x+1);}cnt=0;InOrder(root);return 0;}
C. Ilya and Sticks 题目描述： 有n个木棍，每个木棍都有一个长度，求用其中的木棍组成一些矩形，，求所有矩形的和的最大值。可以将每个木棍的长度减1
每天告诉自己我很棒!
