链接
题意：
给定 $M$ 个城市，每年会选出一个城市举办比赛，现给出前 $N$年城市举办比赛的情况。在接下来的年份中，每年的比赛会在举办比赛次数最小的城市举办，如果有很多城市举办次数均为最小值，则在编号最小的城市举办比赛。现给出 $Q$ 个询问，每次询问第 $K$ 年在哪个城市举办比赛。 $N+1 \le K \le 1e18, 1\le M,N,Q \le 5e5$
分析：
首先我们能想到将其前n个填充到一个这$m$个里面，找到最高点然后高度乘以m，如果超过这个数答案就是，(k-1)%m+1，那如果在这个数之内那？
我们知道我们填充数的时候，先找最矮的，就是出现次数最少的，之后，一样找编号小的，那么我们可以先那前n个提取出来，然后将其前空的个数算出来，之后就可以直接算了。
ll n,m,q;
ll a[maxn],c[maxn];
void solve()
{
scanf("%lld%lld%lld",&n,&m,&q);
for(int i=1;i<=n;i++){
ll k;
scanf("%lld",&k);
a[i]=(c[k]++)*m+k;
}
sort(a+1,a+1+n);
for(int i=1;i<=n;i++) a[i]-=i;
while(q--){
ll k;
scanf("%lld",&k);
k+=lower_bound(a+1,a+n+1,k-n)-a-1-n;
printf("%lld\n",(k-1)%m+1);
}
}
题意：
给你一个$l(2<=l<=100000)$位正整数$n$，将其划分成没有前导0的非空的两段，使这两段表示的正整数之和最小。数据保证至少有一个合法的划分。
分析：
我们就要考虑第二个串从哪个地方开头更优，然后我们知道为了和最小，那么我们想要的的是他们凉饿的长度差最小。
如果总长度为偶数，那么中间两个是$n/2,n/2+1$
如果总长度为奇数，我们认为中间两个数$n/2+1,n/2+2$也可以是 $n/2,n/2+1$
但是枚举方向不要反就行，小的位置往前找第一个不为零的位置，大的位置往后找第一个不为零的位置。这样就能保证长度差最小，然后我们作比较。
- 两种和长度不同选长度小的
相同，从最高位比较选择和更小的那一个。
```c++
ll n;
string str;
ll a[maxn];
ll b[maxn];
ll a1[maxn],b1[maxn];
ll ans[maxn],ans1[maxn];
void solve(){
cin>>n>>str;
str=" "+str;
ll num1,num2;
if(n%2){num1=n/2+1; num2=n/2+2;}
else {num1=n/2; num2=n/2+1;}
ll num=num2;
while(str[num]=='0'){num++;}
ll maxx=1e9+7,maxx1=1e9+7;
ll cnt1=0,cnt2=0;
if(num<=n){for(int i=num-1;i>=1;i--){ a[++cnt1]=str[i]-'0'; } for(int i=n;i>=num;i--){ b[++cnt2]=str[i]-'0'; } maxx=max(cnt1,cnt2); for(int i=1;i<=maxx;i++){ ans[i]+=b[i]+a[i]; ans[i+1]+=ans[i]/10; ans[i]=ans[i]%10; } if(ans[maxx+1]!=0){ maxx++;///changdu }}
num=num1;
while(str[num]=='0'){num--;}
cnt1=0;cnt2=0;if(num>=1){
for(int i=num-1;i>=1;i--){ a1[++cnt1]=str[i]-'0'; } for(int i=n;i>=num;i--){ b1[++cnt2]=str[i]-'0'; } maxx1=max(cnt1,cnt2); for(int i=1;i<=maxx1;i++){ ans1[i]+=b1[i]+a1[i]; ans1[i+1]+=ans1[i]/10; ans1[i]=ans1[i]%10; } if(ans1[maxx1+1]!=0){ maxx1++;///changdu }}
if(maxx1>maxx){
for(int i=maxx;i>=1;i--){ cout<<ans[i]; }}else if(maxx==maxx1){
ll flag=0; for(int i=maxx;i>=1;i--){ if(ans[i]==ans1[i]) continue; else if(ans[i]>ans1[i]){ flag=1; break; }else { flag=0; break; } } if(flag==0){ for(int i=maxx;i>=1;i--){ cout<<ans[i]; } }else { for(int i=maxx1;i>=1;i--){ cout<<ans1[i]; } }}else {
for(int i=maxx1;i>=1;i--){ cout<<ans1[i]; }}
}
[链接]()
--
# 题意：
有个人想要卖国旗
一面国旗可以抽象为一个$n\times m$的矩形，每一个位置有一个颜色。这个矩形由自上而下三条横向的颜色带组成，每一条颜色带宽度相等，而且相邻两个颜色带颜色不能相同。
现在你有一个$n\times m$的矩形，你需要计算其中能够称为国旗的子矩形数量。
# 分析：
首先这样分析：类似一个这样的问题：找出长度为n的字串数量：
如果原长度为5串为$abcde$
>我们选出先选出a长度为1总方案数+1然后加入b长度为2 总方案数+2(b，ab)然后加入c长度为3总方案数+3（c，bc，abc）一次类推，我们能发现出他就是连续方案数的和。其实就是一个(n+1)n/2的变式
那么我们这样看每次我们需要找到三种颜色，我们用x，y，z代表三种颜色，首先x和y一定不能一样，y和z一定不能一样，x和z可以一样，然后我们看x的高度，他的高度一定与y的高度相等，z的高度只要大于x的高度即可，因为我们可以选取高度为x的高度。这样我们急需要维护一个后缀高度数组，然后判断给出的条件即可，
+ 相邻颜色不能一样，三种颜色高度一致。
```c++
ll num[1010][1010];///后缀高度
ll ans, n, m;
char ch[1010][1010];
void solve()
{
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; ++i)
{
scanf("%s", ch[i]+1);
}
/**
* 维护后缀高度
*/
for(int i = n; i >= 1; i--)
{
for(int j = 1; j <= m; j++)
{
if (ch[i][j] == ch[i + 1][j])
{
num[i][j] = num[i + 1][j] + 1;
}
else num[i][j] = 1;
}
}
for (int i = 1; i <= n; i ++)
{
for (int j = 1, k = 0; j <= m; j++)
{
ll hight = num[i][j];///第一种颜色有多高
///不能超过当前n行&&第二种颜色高度一致&&第三种颜色只要大于第一种颜色高度即可&&保证两种相邻颜色不同
if(i + 3 * hight - 1 <= n && num[i + hight][j] == hight && num[i + 2 * hight][j] >= hight && ch[i][j] != ch[i + hight ][j] && ch[i + hight ] != ch[i + 2 * hight ])
{
///每次只要符合条件结果方案书就会+1
///以前有宽度&&第一种颜色当前列与前一列颜色相同&&前1列的高度也是h&&同理判断第二种颜色，第三种颜色
if(k && ch[i][j] == ch[i][j - 1] && num[i][j - 1] == hight && ch[i + hight][j] == ch[i + hight][j - 1] && num[i + hight ][j - 1] == hight && ch[i + 2 * hight][j] == ch[i + 2 * hight][j - 1] && num[i + 2 * hight][j - 1] >= hight)
{
k++;
}
else k = 1; ///宽度为1
}
else k = 0;
ans += k;
}
}
printf("%lld\n", ans);
}
