2021CCPC湘潭全国邀请赛题解

题意：

给定a和b，求a+b,a+b如果大于1023或者小于-1024，就自动溢出

思路：模拟

比如1023+1=1024，1024>1023 就自动溢出成-1024，模拟即可

时间复杂度：O n

#include
#define fer(i,a,b) for(re i = a ; i <= b ; ++ i)
#define re register int
#define pll pair<int,int> 
#define x first 
#define y second 
#define sf(x) scanf("%d",&x)
#define sfl(x) scanf("%lld",&x)
typedef long long ll ;
using namespace std;
const int N =  1e6 + 10 , M = 1010 , inf = 0x3f3f3f3f , mod = 1e9 + 7 ;int main()
{int t ;cin >> t ;while(t--){int a , b ;cin >> a >> b ;int k = a + b ;if(k > 1023) k -= 2048 ;else if(k < -1024) k += 2048 ;cout << k << "\n" ;}return 0;
}

题意：

给定x1,x2,y1,y2
求
答案对1e9+7取模

思路：数论分块

一维数论整除分块
第4个式子的答案有点问题
对其每一个区间左端点为l，右端点为r，值为cnt
答案为(r-l+1) $\times$ cnt $\times$ ∑ i = x 1 x 2 ⌊ i x 1 ⌋ \sum_{i=x1}^{x2} {\lfloor \frac{i}{x1} \rfloor} ∑i=x1x2​⌊x1i​⌋
在考虑一下 求
∑ i = x 1 x 2 ⌊ i x 1 ⌋ \sum_{i=x1}^{x2} {\lfloor \frac{i}{x1} \rfloor} ∑i=x1x2​⌊x1i​⌋

可以发现，
当x1<=i<2*x1 ，i/x1等于1
当2*x1<=i<3*x1,i/x1等于2
...........
当n*x1<=i<(n+1)*x1 , i/x1等于n
因此答案为 x1 * (1 + 2 + ........ + n ) + 大于等于(n+1)*x1的部分暴力求
在考虑一下1式
答案为 x1 * (1^2 + 2^2 + ........ + n^2) + 大于等于(n+1)*x1的部分暴力求
中间括号的部分用公式o1求即可

时间复杂度：O t n \sqrt{n} n ​

#include 
using namespace std;
typedef long long ll;
const int  mod = 1e9 + 7;ll qpow(ll a, ll b) {ll res = 1;while (b) {if (b & 1)res = res * a % mod;a = a * a % mod;b >>= 1;}return res;
}
ll inv6 = qpow(6, mod - 2);
ll inv2 = qpow(2, mod - 2);ll cal_a2(ll x1, ll x2) {ll a = 0;ll k = x2 / x1 - 1;ll k2 = x2 / x1;ll k1 = x2 % x1 + 1;a = x1 * k % mod * (k + 1) % mod * (2 * k + 1) % mod * inv6 % mod;a = (a + k1 % mod * k2 % mod * k2 % mod) % mod;return a;
}ll cal_b2(ll x1, ll x2) {ll b = 0;for (ll l = x1, r; l <= x2; l = r + 1) {r = x2 / (x2 / l);b += (r - l + 1) * (x2 / l) % mod * (x2 / l) % mod;b %= mod;}return b;
}ll cal_a(ll x1, ll x2) {ll a1 = 0;ll k = x2 / x1 - 1;ll k2 = x2 / x1;ll k1 = x2 % x1 + 1;a1 = (a1 + x1 * k % mod * (1 + k) % mod * inv2 % mod) % mod;a1 = (a1 + k1 * k2 % mod) % mod;return a1;
}ll cal_b(ll x1, ll x2) {ll b = 0;for (ll l = x1, r; l <= x2; l = r + 1) {r = x2 / (x2 / l);b += (r - l + 1) * (x2 / l);b %= mod;}return b;
}ll cal_ab(ll x1, ll x2) {ll ab = 0;for (ll l = x1, r; l <= x2; l = r + 1) {r = x2 / (x2 / l);ll v = x2 / l;ll f = cal_a(x1, r) - cal_a(x1, l - 1);f = (f + mod) % mod;ab = (ab + v * f % mod) % mod;}return ab;
}int main() {int t;cin >> t;while (t--) {ll x1, x2, y1, y2;cin >> x1 >> x2 >> y1 >> y2;ll a1 = 0, b1 = 0, c1 = 0, d1 = 0;//b d quell dx = x2 - x1 + 1;ll dy = y2 - y1 + 1;a1 = cal_a2(x1, x2) % mod;b1 = cal_b2(x1, x2) % mod;c1 = cal_a2(y1, y2) % mod;d1 = cal_b2(y1, y2) % mod;ll a = 0, b = 0, c = 0, d = 0;a = cal_a(x1, x2);c = cal_a(y1, y2);b = cal_b(x1, x2);d = cal_b(y1, y2);ll ab = 0, cd = 0;ab = cal_ab(x1, x2) * dy % mod;cd = cal_ab(y1, y2) * dx % mod;ll ans = 0;ans = (ans + (((dy * a1 % mod + dy * b1 % mod) % mod + dx * c1 % mod) % mod + dx * d1 % mod) % mod) % mod;ans = (ans + 2 * ab % mod) % mod;ans = (ans + 2 * a * c % mod) % mod;ans = (ans + 2 * a * d % mod) % mod;ans = (ans + 2 * b * c % mod) % mod;ans = (ans + 2 * b * d % mod) % mod;ans = (ans + 2 * cd % mod) % mod;ans %= mod;printf("%lld\n", ans);}return 0;
}

题意：

给一个整数n，会有2^n个不同的cp字符串
求每个不同字符串的ccpc子串的个数的总和
答案对1e9+7取膜

思路：bm算法求线性通项公式

先暴力预处理前20项
然后在用bm算法求出线性递推方程
o1输出即可

时间复杂度：20 * 2^20 + t

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// headint _;
ll n;
namespace linear_seq {const int N=10010;ll res[N],base[N],_c[N],_md[N];vector<int> Md;ll mul(ll *a,ll *b,int k) {rep(i,0,k+k) _c[i]=0;rep(i,0,k) if (a[i]) rep(j,0,k) _c[i+j]=(_c[i+j]+a[i]*b[j])%mod;for (int i=k+k-1;i>=k;i--) if (_c[i])rep(j,0,SZ(Md)) _c[i-k+Md[j]]=(_c[i-k+Md[j]]-_c[i]*_md[Md[j]])%mod;rep(i,0,k) a[i]=_c[i];}ll solve(ll n,VI a,VI b) { // a 绯绘暟 b 鍒濆€?b[n+1]=a[0]*b[n]+...
//        printf("%d\n",SZ(b));ll ans=0,pnt=0;int k=SZ(a);assert(SZ(a)==SZ(b));rep(i,0,k) _md[k-1-i]=-a[i];_md[k]=1;Md.clear();rep(i,0,k) if (_md[i]!=0) Md.push_back(i);rep(i,0,k) res[i]=base[i]=0;res[0]=1;while ((1ll<<pnt)<=n) pnt++;for (int p=pnt;p>=0;p--) {mul(res,res,k);if ((n>>p)&1) {for (int i=k-1;i>=0;i--) res[i+1]=res[i];res[0]=0;rep(j,0,SZ(Md)) res[Md[j]]=(res[Md[j]]-res[k]*_md[Md[j]])%mod;}}rep(i,0,k) ans=(ans+res[i]*b[i])%mod;if (ans<0) ans+=mod;return ans;}VI BM(VI s) {VI C(1,1),B(1,1);int L=0,m=1,b=1;rep(n,0,SZ(s)) {ll d=0;rep(i,0,L+1) d=(d+(ll)C[i]*s[n-i])%mod;if (d==0) ++m;else if (2*L<=n) {VI T=C;ll c=mod-d*powmod(b,mod-2)%mod;while (SZ(C)<SZ(B)+m) C.pb(0);rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;L=n+1-L; B=T; b=d; m=1;} else {ll c=mod-d*powmod(b,mod-2)%mod;while (SZ(C)<SZ(B)+m) C.pb(0);rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;++m;}}return C;}ll gao(VI a,ll n) {VI c=BM(a);c.erase(c.begin());rep(i,0,SZ(c)) c[i]=(mod-c[i])%mod;return solve(n,c,VI(a.begin(),a.begin()+SZ(c)));}
};int main() {int t;scanf("%d",&t);vector<int>v;for(int i=1;i<=20;i++){ll ans=0;char s[22];s[i]=0;for(int j=0;j<(1<<i);j++){for(int k=0;k<i;k++){if((1ll<<k)&j){s[k]='C';}else s[k]='P';}
//        		cout<for(int k=0;k+3<i;k++){if(s[k]=='C'&&s[k+1]=='C'&&s[k+2]=='P'&&s[k+3]=='C'){ans++;k=k+3;}}}//printf("%lld\n",ans);v.push_back(ans);}while (t--) {scanf("%lld",&n);printf("%lld\n",linear_seq::gao(v,n-1));}
}

题意：

给定n个在set里面的数，每次可以进行一次操作
将set里面的其中一个数x变成 x-9 / x-99 / x-999 / ........ /x − (10^k − 1) 
保证x − (10^k − 1) > 0
并且每个数在set里面不能同时出现多次
A先操作，然后B操作，谁最后不能操作就输，问谁赢

思路：数论，贪心

性质1：任何一个数都可以表示成9*a+b的形式
性质2：如果减去一个数，一定只减9,因为减99等价于减去了11个9
所以都是奇数次操作，不影响最后的答案
性质3：从最小的数开始减，减到不能减为止
前2个性质都比较好推，说一下第三个是怎么推出来的
比如 111 * 9 + 1 和 11 * 9 + 1 我们考虑一下顺序
如果先减111 * 9 + 1的话，会发现只能减到12 * 9 + 1 
在减的话变成11 * 9 + 1 ，与另外一个11 * 9 + 1冲突
所以从最小的开始减，减到0*9+1，第二个数减到1*9+1，以此类推。
最后统计一下操作数
如果操作数为偶数，B赢
否则，A赢

时间复杂度：O tnlogn

#include
#define fer(i,a,b) for(re i = a ; i <= b ; ++ i)
#define re register int
#define pll pair<int,int> 
#define x first 
#define y second 
#define sf(x) scanf("%d",&x)
#define sfl(x) scanf("%lld",&x)
typedef long long ll ;
using namespace std;
const int N =  1e5 + 10 , M = 1010 , inf = 0x3f3f3f3f , mod = 1e9 + 7 ;
int n ;int main()
{int t ;cin >> t ;while(t--){int a[N] = {0} ;vector<int> q[20] ;cin >> n ;fer(i,1,n){sf(a[i]) ;q[a[i] % 9].push_back(a[i]) ;}int sum = 0 ;for(int i = 0 ; i < 9 ; i ++){sort(q[i].begin(),q[i].end()) ;if(i == 0){for(int j = 0 ; j < q[i].size() ; j ++){sum += ((q[i][j] / 9 - 1) - j > 0 ? q[i][j] / 9 - 1 - j : 0 );}}else{for(int j = 0 ; j < q[i].size() ; j ++){sum += ((q[i][j] / 9 ) - j > 0 ? q[i][j] / 9 - j : 0 );}}}if(sum & 1) puts("A");else puts("B") ;}return 0;
}

题意：

给定n个栈，每个栈i一开始都有一个数i
m次操作，每次操作给出2个数a，b
将a这个栈的所有数一个一个弹出来放到b里面去
求最后每个栈的元素个数以及是哪些数

思路：图论，双链表

发现数据n是1e5,暴力最坏情况下是on^2，会超时
考虑一下优化
入手点是将A这个栈中的数都弹出来放在B中
等价于A栈的头和B栈的头连了一条边
所以用2个变量维护每个栈的头尾节点
不断的进行连边，最后输出的答案的时候
从头结点开始遍历这条链
连边我连的双向边，不用考虑方向
最后遍历的时候记录一下父亲节点即可
最后要考虑一下三种情况
A，B非空
A空，B非空
A非空，B空
分情况讨论一下

时间复杂度：O nt

#include
#define fer(i,a,b) for(re i = a ; i <= b ; ++ i)
#define re register int
#define pll pair<int,int> 
#define x first 
#define y second 
#define sf(x) scanf("%d",&x)
#define sfl(x) scanf("%lld",&x)
typedef long long ll ;
using namespace std;
const int N =  1e5 + 10 , M = 2 * N , inf = 0x3f3f3f3f , mod = 1e9 + 7 ;
int t , n , m ;
int k ;
int b[N] ;
struct ai{int l ,r ;
}q[N] ;
int h[N] , e[M] , ne[M] , idx ;
void add(int a , int b)
{e[idx] = b , ne[idx] = h[a] , h[a] = idx ++ ;
}
void dfs(int u , int fa)
{for(int i = h[u] ; i != -1 ; i = ne[i]){int j = e[i] ;if(j == fa) continue ;b[++ k] = j ;dfs(j,u) ;}
}
int main()
{cin >> t ;while(t--){cin >> n >> m ;memset(h,-1,sizeof h) ;idx = 0 ;for(int i = 1 ; i <= n ; i ++){q[i].l = q[i].r = i ;}while(m--){int a , b ;sf(a) , sf(b) ;if(q[a].l && q[b].l) // a , b 非空{add(q[a].l,q[b].l) ;add(q[b].l,q[a].l) ;q[b].l = q[a].r ;q[a].l = q[a].r = 0 ;}else if(q[a].l && !q[b].l) // a非空 , b空{q[b].l = q[a].r ;q[b].r = q[a].l ;q[a].l = q[a].r = 0 ;}}for(int i = 1 ; i <= n ; i ++){if(!q[i].l){puts("0");}else{k = 0 ;dfs(q[i].l,-1) ;cout << k + 1 << " " ;cout << q[i].l << " " ;for(int i = 1 ; i <= k ; i ++)cout << b[i] << " " ;cout << "\n" ;}}}return 0;
}

题意：

您将得到一个仅包含小写字母的字符串S[1..N]。现在你需要找到最长的
子串S[l..r]使得每个字母（“a”到“z”）在子串中出现的次数不超过K次。你只
需要输出长度（r− 最长子串的l+1）。

思路：双指针

双指针模拟一下即可

时间复杂度：O tn

#include
#define fer(i,a,b) for(re i = a ; i <= b ; ++ i)
#define re register int
#define pll pair<int,int> 
#define x first 
#define y second 
#define sf(x) scanf("%d",&x)
#define sfl(x) scanf("%lld",&x)
typedef long long ll ;
using namespace std;
const int N =  1e6 + 10 , M = 2010 , inf = 0x3f3f3f3f , mod = 1e9 + 7 ;int main()
{int t ;cin >> t ;while(t--){int k ;string a ;cin >> k >> a ;map<char,int> q ;int res = 0 ;for(int l = 0 , r = 0 ; l < a.size() ; l ++){while(r < a.size() && q[a[r]] < k){q[a[r]] ++ ;r ++ ;}//cout << l << " " << r << "\n" ;res = max(res,r-l) ;q[a[l]] -- ;}cout << res << "\n" ;}return 0;
}

最后给大家看看奖状吧