好好复习初赛，我压线过的
瞎搞的封面
1.分糖果
一般来说T1都不会太难，其实他还是不是很难
我太蒻了，考场半小时才想出来
咳咳，一看数据范围有有 10^9，一看就不是用暴力做的。
假如有n个小朋友（包括你），你搬了k块糖果，那么你最终得到的奖励就是 k mod n 块糖果。也就是说，假如你最少搬l块糖果，最多搬k块糖果，你如果要得到最多的奖励，就要在l到r之间选一个数，使得这个数模n的值最大。
那么最优的情况下会剩 n - 1 块糖果，当然，样例 2告诉我们，有时候我们没法这么贪心，可能最优的结果达不到 n - 1，那么就说明，在l到r之间，数越大，模n的值就越大。所以对于这种情况，就直接拿r块糖果，结果一定是最优的。而其他情况最优值就是n - 1。
那么，你们要的代码来了：
#include<bits/stdc++.h>
using namespace std;
int n,l,r;
int main(){
cin>>n>>l>>r;
cout<<min(r,l+(n-1-l%n))%n; //先尝试将余数补到n-1，如果超过r，那么结果就是r mod n，否则就是n-1
return 0;
}
2.插入排序
T2不是很难，避下坑就好了
由于给的条件是修改次数不超过 5000，我们应该在修改处做文章。
注意到一个数组 a进行“示范代码”之后，数ai 在 aj 之前的充要条件是以下两者中成立一个：
-
<a
-
且i<j
考虑维护一个数组b储存各个数在数组a中的相对排名，那么开始输入a时进行统计（用以上两条判断）之后：
每进行一次操作 2 ，输出。
每进行一次操作 1 ，即将修改成v。此时用O(n) 遍历数组中的各个元素，如果某一个元素i满足在数组插入排序后原本在x之前，现在在x之后（仍然用两条判定），因为i与数组中其他数的相对位置没有变化，使
增加一，
减少一即可。另外一种情况同理。
#include<bits/stdc++.h>
using namespace std;
int n,q,a[8005],b[8005],num,x,v,ans;
int main()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
if(i==j||a[j]<a[i]||a[j]==a[i])b[i]++;
else b[j]++;
}//这里的b[i]就是第i个数在数组a[i]中的排位
}
for(int i=0;i<q;i++)
{
scanf("%d",&num);
if(num==1)
{
scanf("%d%d",&x,&v);
for(int i=1;i<=n;i++)
{
if(i==x)continue;
if((a[i]<a[x]||a[i]==a[x]&&i<x)&&(a[i]>v||a[i]==v&&i>x))
{
b[i]++;b[x]--;
}
else if((a[i]>a[x]||a[i]==a[x]&&i>x)&&(a[i]<v||a[i]==v&&i<x))
{
b[i]--;b[x]++;
}
}
a[x]=v;
}
if(num==2)
{
scanf("%d",&x);
printf("%d\n",b[x]);
}
}
return 0;
}3.网络连接
T3按理来说比较难，但是今年比较简单
看到需要由地址串映射到计算机编号，我们可以考虑使用 map。这里推荐使用用法基本相似但查询、修改复杂度均为 O(1)的 unordered_map（需要用到 C++11，若在本地无法编译则要加上编译选项）。
思路
- 先判断每台计算机提供的地址串是否符合规范，若不符合，直接输出
ERR； - 对于每台服务器（
Server）提供的地址串，先在unordered_map中寻找该地址串是否已经建立映射（即是否已经有服务器提供相同地址串以建立连接），若已有则输出FAIL，否则建立映射并输出OK； - 对于每台客户机 （
Client）提供的地址串，先在unordered_map中寻找该地址串是否已经建立映射（即是否已经有服务器提供该地址串以建立连接），若已有则该客户机可以加入连接，此时输出建立连接的服务器的编号，否则该客户机不能加入连接，输出FAIL。
这里先简单介绍一下 unordered_map 。unordered_map 本质上就像一个数组，
只不过你可以自己定义键和值 （其实就是下标与它所对应的元素） 类型。
unordered_map<string,int> mp; 这样你就有了一个可以用 string 类型映射到 int 类型的 unordered_map 数组 mp 。
mp["hello"] = 532;这意味着在 mp数组里，"hello" 对应着532 。
mp.count("hello");
mp.count("world");判断该元素之前是否存在映射。 返回值分别为1和0。map 的用法则与其相似，这里不再赘述。
判断地址串是否存在的部分可以用 unordered_map 解决，那么整道题的重点则落在了如何判断地址串是否规范上。
我们先列出地址串不符合规范的所有可能形式。
- 形如
a.b.c.d:e，其中整数a,b,c,d,e 有一个数超过题目给定的范围（即 0≤a,b,c,d≤255≤e≤65535），或有一个数含有前导 0。
针对这种情况，我们可以用如下的方法依次提取a,b,c,d,e，并判断其是否在规定范围内。
bool check(string s)
{
int len = s.length();
long long tmp = 0;
for(int i=0;i<len;i++)
{
if(s[i]=='.'||s[i]==':')
{
if(0<=tmp&&tmp<=255) //判断a,b,c,d是否符合规范
{
tmp = 0; //清零
continue;
}
else return false;
}
else if(s[i]<'0'||s[i]>'9') return false;
if(i&&!tmp&&s[i-1]=='0') return false; //这一行用来判断前导0
tmp = tmp*10+s[i]-'0'; //读取数字
}
if(0<=tmp&&tmp<=65535) return true; //判断e是否符合规范
else return false;
}- 形如
a.b.c:d.e，其中字符.或:出现的顺序不规范。
针对这种情况，我们可以用计数器分别记录.和:出现的次数，判断:出现时，.出现的次数是否为 3。
int cnt1=0,cnt2=0,cnt3=0;
for(int i=0;i<len;i++)
{
if(s[i]=='.'||s[i]==':')
{
if(s[i]=='.') cnt1++;
else if(s[i]==':') cnt2++;
if(cnt1<3&&cnt2) return false; //出现顺序是否规范
/*
判断a,b,c,d的范围是否规范
*/
}
else if(s[i]<'0'||s[i]>'9') return false;
/*
判断前导0 以及提取数字
*/
}-
形如
a..b.c:e或a.b.c:.e，其中字符.或:连着出现。
这时候符号的数量符合规范，但数字的数量不符合规范。可以仿照情况2，用计数器记录数字出现的次数，并在最后判断字符和数字出现的次数是否符合规范。 -
形如
.a.b.c:e或a.b.c.d:，其中字符.或:出现在地址串头尾。 针对字符出现在头的情况，我们可以在字符出现时判断是否已有数字出现；针对字符出现在尾的情况，可以用情况3的方法来解决。
这两种情况都需要加上数字的计数器。
int len = s.length();
long long tmp = 0;
int cnt1=0,cnt2=0,cnt3=0;
for(int i=0;i<len;i++)
{
if((i==0||(s[i-1]=='.'||s[i-1]==':'))&&s[i]>='0'&&s[i]<='9') cnt3++;
//如果当前为第一个位置或前一个为字符，并且这个位置为数字
if(s[i]=='.'||s[i]==':')
{
/*
统计字符出现的次数
*/
if(cnt1<3&&cnt2) return false; //出现顺序是否规范
if(!cnt3) return false; //如果字符在第一个数字前出现
/*
判断a,b,c,d的范围是否规范
*/
}
else if(s[i]<'0'||s[i]>'9') return false;
/*
判断前导0 以及提取数字
*/
}
if(cnt1!=3||cnt2!=1||cnt3!=5) return false; //判断字符、数字出现的数量
/*
判断e的范围是否规范
*/将上述4种情况的解决方案拼在一起，就得到判断地址串是否规范的函数。
Code
#include <bits/stdc++.h>
using namespace std;
int n;
unordered_map<string,int>address;
bool check(string s)
{
int len = s.length();
long long tmp = 0;
int cnt1=0,cnt2=0,cnt3=0;
for(int i=0;i<len;i++)
{
if((i==0||(s[i-1]=='.'||s[i-1]==':'))&&s[i]>='0'&&s[i]<='9') cnt3++;
//如果当前为第一个位置或前一个为字符，并且这个位置为数字
if(s[i]=='.'||s[i]==':')
{
if(s[i]=='.') cnt1++;
else if(s[i]==':') cnt2++;
//统计字符出现的次数
if(cnt1<3&&cnt2) return false; //出现顺序是否规范
if(!cnt3) return false; //如果字符在第一个数字前出现
if(0<=tmp&&tmp<=255) //判断a,b,c,d的范围是否规范
{
tmp = 0;
continue;
}
else return false;
}
else if(s[i]<'0'||s[i]>'9') return false; //出现了奇怪的字符
if(i&&!tmp&&s[i-1]=='0') return false; //判断前导 0
tmp = tmp*10+s[i]-'0'; //提取数字
}
if(cnt1!=3||cnt2!=1||cnt3!=5) return false; //字符和数字出现的数量是否正确
if(0<=tmp&&tmp<=65535) return true; //判断e的范围
else return false;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
string cpt,adr;
cin>>cpt>>adr;
if(!check(adr)) puts("ERR"); //如果地址串不符合规范
else if(cpt=="Server")
{
if(address.count(adr)) puts("FAIL");
else
{
address[adr] = i;
puts("OK");
}
}
else if(cpt=="Client")
{
if(address.count(adr)) printf("%d\n",address[adr]);
else puts("FAIL");
}
}
return 0;
}4.小熊的果篮
今年的T4比T3还水
首先对输入序列建双向链表，维护每一个“假块”头建双向链表，共维护两个链表。
这里的“假块”指每个“假块”中水果种类必定相同，但相邻“假块”中水果种类可能相同。
我们可以使用双向链表的删除元素来模拟吃一个水果。
不断循环遍历“假块”头链表，遍历过程中记录上一个被吃水果种类。遍历到某个块头时，若其指向的水果与上一个被吃水果种类相同，直接将这个块头删除，相当于合并块；若不同，吃掉这个水果，更新上一个被吃水果种类，将这个块头指向的水果变成被吃水果的下一个水果。
关于一个假块被吃完的处理方法，此时这个假块的块头一定会指向下一个块头。若这个块头的种类与被吃水果的种类不同，删掉这个块，因为遍历下一个块时将会吃掉这个水果；若相同，不动，因为接下来的过程将会把下一个块的块头删除。这样保证遍历时不会出现长度小于一的假块。若假块没有被吃完，其指向的下一个水果一定与吃掉的种类相同，同样不做任何处理。
每个水果被遍历一次，每个块被删除一次，时间复杂度Θ(n)。
代码如下：
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int MAXN = 2e5+10;
struct Node{
int prev;
int val;
int next;
};
int n;
int shuiguo[MAXN];
Node headList[MAXN];
Node shuiguoList[MAXN];
int cc;
void EatOne(int pos) {
int prev = shuiguoList[pos].prev;
int next = shuiguoList[pos].next;
shuiguoList[prev].next = next;
shuiguoList[next].prev = prev;
printf("%d ", pos);
}
void Del(int pos) {
int prev = headList[pos].prev;
int next = headList[pos].next;
headList[prev].next = next;
headList[next].prev = prev;
}
void Chi() {
int solo = headList[0].next;
int nowcolor = shuiguo[headList[solo].val];
while (solo!=cc+1) {
if (shuiguo[headList[solo].val]!=nowcolor) {
Del(solo);
solo = headList[solo].next;
continue;
}
EatOne(headList[solo].val);
headList[solo].val = shuiguoList[headList[solo].val].next;
if (shuiguo[headList[solo].val]!=nowcolor) {
Del(solo);
}
solo = headList[solo].next;
nowcolor^=1;
}
putchar('\n');
}
int main() {
scanf("%d", &n);
shuiguoList[0].next = 1;
for (int i = 1; i <= n; i++) {
scanf("%d", &shuiguo[i]);
shuiguoList[i].prev = i-1;
shuiguoList[i].next = i+1;
}
shuiguo[0] = 2;
shuiguo[n+1] = 2;
headList[0].next = 1;
for (int i = 1; i <= n; i++) {
if (shuiguo[i]!=shuiguo[i-1]) {
cc++;
headList[cc].prev = cc-1;
headList[cc].next = cc+1;
headList[cc].val = i;
}
}
while (shuiguoList[0].next!=n+1) {
Chi();
}
return 0;
}
今年CSP初赛比复赛都难，但还是要祝您复赛AK，加油。