写在前面
全是数学题好恶心。出题人数据造的很好，下次别造了。
A
数据太弱，模拟即可。浪费了十分钟想线段树。
#include <bits/stdc++.h>
using namespace std;
long long mod = 998244353;
#define N 8000005
using i64 = long long;
int tree[N];//tree存树 n为数组下标
long long n;
int lowbit(int x)
{
return x & -x;
}
i64 qry(int x)//查询闭区间 [1,x] 的前缀和
{
i64 res = 0;
for (int i = x; i > 0; i -= lowbit(i))
res += tree[i];
return res;
}
void upd(int l, int z)//向闭区间 [l,n] 加上数值 z
{
for (int i = l; i <= n; i += lowbit(i))
tree[i] += z;
}
void solve()
{
}
/*
使用:
前缀和树状数组:
-upd(i, z) <使区间 [i,n] 加上 z>
-qry(y) - qry(x - 1) <查询[x,y]的区间和>
差分树状数组:
-upd(x, z), upd(y + 1, -z) <同时使用，使区间 [x,y] 每个数都加上 z>
-qry(x) <查询数组下标为 x 的值>
*/
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
long long t, l, r, k, flag, x, temp, last, maxx, sub, m, y, op;
long long summ;
long long q[200005];
long long qz[200005];
long long er[200005];
long long per[200005];
per[0] = 1;
for(int i = 1; i <= 1000005; i++){
per[i] = per[i-1] * 2;
per[i]%=mod;
}
cin>>n;
cin>>m;
string s;
s.clear();
cin>>s;
for(int i = 1; i <= n; i++){
q[i] = s[i-1] - '0';
//printf("%d ", q[i]);
}
//printf("\n");
qz[0] = 0;
er[0] = 0;
for(int i = 1; i <= n; i++){
if(q[i]==0){
qz[i] = qz[i-1] + 1;
}
else{
qz[i] = qz[i-1] * 2;
}
qz[i] %= mod;
er[i] = er[i-1] + q[i];
}
for(int i = 1; i <= m; i++){
cin>>op;
if(op==1){
cin>>sub;
q[sub] = 1-q[sub];
}
else{
cin>>x;
cin>>l;
cin>>r;
temp = x;
for(int j = l; j <= r; j++){
if(q[j]==0){
temp++;
}
else{
temp*=2;
}
temp%=mod;
}
printf("%lld\n", temp);
}
}
return 0;
}
B
赛时推测是拓展卢卡斯定理，但没调出来。考虑n个相同物体放入m个不同的可以为空的盒子，即求 。要注意的是
可能是合数。
C
树上差分。每次操作对节点 加上
，最后跑一遍树上前缀和统计答案。
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define lowbit(x) ((x)&(-(x)))
#define foru(i,begin,end) for(i=begin;i<=end;i++)
#define ford(i,begin,end) for(i=begin;i>=end;i--)
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define maxheap(x) priority_queue<x,vector<x>,less<x> >
#define minheap(x) priority_queue<x,vector<x>,greater<x> >
#define endl '\n'
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
typedef long long ll;
typedef unsigned long long ull;
//#define mod 1000000009
//#define mod 1000000007
vector<int> es[100005];
ll val[100005];
ll d[100005];
int fa[100005];
ll ans[100005];
void getans(int x,int pa,int sum)
{
ans[x]=sum+val[x]+d[x];
for(auto i:es[x])
{
if(i==pa) continue;
getans(i,x,sum+d[x]);
}
}
int main()
{
int n,m;
cin>>n>>m;
int i;
for(i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
es[u].push_back(v);
es[v].push_back(u);
}
for(i=1;i<=n;i++) cin>>val[i];
d[0]=val[1];
//foru(i,0,n) cout<<d[i]<<' ';
for(i=1;i<=m;i++)
{
int op,x,y;
cin>>op>>x>>y;
if(op==1)
{
d[x]+=y;
}
else d[x]-=y;
}
//foru(i,1,n) cout<<d[i]<<' ';
getans(1,0,0);
foru(i,1,n) cout<<ans[i]<<' ';
return 0;
}
D
一开始尝试差分加离散化，但由于题目与样例歧义的描述wa了，队友发挥聪明才智改用优先队列，将每个区间按左端点排序，对于每个区间，弹出堆中离开时间早于区间加入时间的人，再将其入队，优先队列的大小即为当前时间的人数。
#include <bits/stdc++.h>
using namespace std;
long long xx[1000005];
long long yy[1000005];
long long subb[1000005];
bool cmp(long long x, long long y){
return xx[x] < xx[y];
}
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
long long t, n, l, r, k, flag, x, temp, last, maxx, sub, m, y;
long long summ;
priority_queue<long long, vector<long long>, greater<long long>> pq;
cin>>n;
for(int i = 1; i <= n; i++){
cin>>xx[i];
cin>>yy[i];
subb[i] = i;
}
sort(subb+1,subb+1+n,cmp);
maxx = 0;
for(int i = 1; i <= n; i++){
sub = subb[i];
x = xx[sub];
y = yy[sub];
pq.push(y);
while(!pq.empty()){
temp = pq.top();
//printf("%lld\n", temp);
if(temp<=x){
pq.pop();
}
else{
break;
}
}
temp = pq.size();
//printf("%lld %d %lld %lld\n", temp, i, x, y);
maxx = max(maxx,temp);
}
printf("%lld\n", maxx);
return 0;
}
E
和C差不多，记录一下先后顺序就行。
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <vector>
using namespace std;
int fa[200001] ;
vector <int> son[200001];
int cg[200001];
int nm[200001];
int co[200001];
void dfs(int x,int color){
if(co[x])
return ;
else{
co[x]=color;
for(int i=0;i<son[x].size();i++){
int y=son[x][i];
dfs(y,color);
}
}
return ;
}
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n-1;i++){
int x;
scanf("%d",&x);
fa[i+1]=x;
son[x].push_back(i+1);
}
int q;
scanf("%d",&q);
for(int i=1;i<=q;i++)
scanf("%d %d",&cg[i],&nm[i]);
for(int i=q;i>=1;i--){
dfs(cg[i],nm[i]);
}
for(int i=1;i<=n;i++)
printf("%d ",co[i]);
}
F
数据好像也很弱，模拟即可。
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
int x[1001];
int y[1001];
bool check(int x,int y,int xq,int yq){
if(x<xq || y<yq)
return 0;
if(x==xq && y==yq)
return 1;
if(x==y)
return 0;
if(x>y){
if(xq>yq){
if(y==yq){
if((x-xq)%y==0)
return 1;
else
return 0;
}
else
return check(x-y,y,xq,yq);
}
else
return check(x-y,y,xq,yq);
}
else{
if(xq<yq){
if(x==xq){
if((y-yq)%x==0)
return 1;
else
return 0;
}
else
return check(x,y-x,xq,yq);
}
else
return check(x,y-x,xq,yq);
}
}
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d %d",&x[i],&y[i]);
int q;
scanf("%d",&q);
for(int i=1;i<=q;i++){
int count=0;
int xq,yq;
scanf("%d %d",&xq,&yq);
for(int j=1;j<=n;j++){
if(check(x[j],y[j],xq,yq))
count++;
}
printf("%d\n",count);
}
}
G
不错的思维题。对于某两个数 和
，显然其积的末尾
的个数等于
和
末尾
的个数之和加上其能被
和
整除的次数。开数组统计一下末尾
的个数和其能被
和
整除的次数，用双指针处理一下即可。
#include <bits/stdc++.h>
using namespace std;
long long a[200005];
long long ling[200005];
long long er[200005];
long long wu[200005];
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
long long t, n, l, r, k, flag, x, temp, last, maxx, sub, m, y;
long long summ;
cin>>n;
cin>>k;
for(int i = 1; i <= n; i++){
cin>>a[i];
temp = a[i];
ling[i-1] = 0;
x = 0;
flag = 1;
while(temp>0){
y = temp%10;
if(y==0&&flag==1){
x++;
}
else{
flag = 0;
ling[i-1] = max(ling[i-1], x);
x = 0;
}
temp/=10;
}
while(a[i]%10==0){
a[i]/=10;
}
temp = a[i];
er[i-1] = 0;
while(temp%2==0){
temp/=2;
er[i-1]++;
}
temp = a[i];
wu[i-1] = 0;
while(temp%5==0){
temp/=5;
wu[i-1]++;
}
//printf("%lld ",ling[i]);
}
long long ans=0,sum=0,j=0;
long long s2, s5;
s2 = 0;
s5 = 0;
for(int i=0;i<n;i++)
{
sum+=ling[i];
s2 += er[i];
s5 += wu[i];
if((sum+min(s2,s5))>=k)
{
ans+=(n-i);
while(j<=i)
{
sum-=ling[j];
s2-=er[j];
s5-=wu[j];
j++;
if((sum+min(s2,s5))>=k){
ans+=(n-i);
}
else{
break;
}
}
}
}
cout<<ans<<endl;
//printf("\n");
return 0;
}
H
大模拟，细节很多，由于 最大为
，可以分类讨论。可能有更简单的方法，但是懒得动脑子了。
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
int t[10];
int main(){
int n,k;
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
t[x%k]++;
}
if(t[0])
printf("0\n");
else{
if(n==1){
for(int i=1;i<=k-1;i++){
if(t[i])
{
printf("%d\n",k-i);
return 0;
}
}
}
switch(k){
case 2:{
printf("1\n");
}break;
case 3:{
if(t[2])
printf("1\n");
else
printf("2\n");
}break;
case 4:{
if(t[2]>=2)
printf("0\n");
else{
if(t[3])
printf("1\n");
else{
if(t[2])
printf("1\n");
else
printf("2\n");
}
}
}break;
case 5:{
if(t[4])
printf("1\n");
else
if(t[3])
printf("2\n");
else
if(t[2])
printf("3\n");
else
printf("4\n");
}break;
case 6:{
if(t[2]&& t[3] || t[3] && t[4])
printf("0\n");
else{
if(t[5])
printf("1\n");
else
if(t[4]){
if(t[2])
printf("1\n");
else
printf("2\n");
}
else{
if(t[3])
printf("1\n");
else{
if(t[2]){
if(t[2]>=2)
printf("1\n");
else
printf("2\n");
}
else
printf("3\n");
}
}
}
}break;
}
}
return 0;
}
I
算法板子，网上偷一个过来就能求出所有回文串。用线段树维护每个回文串能取到的最大值，可以在
的复杂度内完成。不过这个题数据好像也很弱，赛后看代码有一堆暴力扫描过的，造数据的背大锅。
#include <bits/stdc++.h>
using namespace std;
long long v[205];
#define ll long long
#define MAX_LEN 4000005
ll seg_tree[MAX_LEN << 2];
ll Lazy[MAX_LEN << 2];
ll arr[MAX_LEN];
//从下往上更新 节点
void push_up (ll root) {
seg_tree[root] = max(seg_tree[root << 1], seg_tree[root << 1 | 1]); //最小值改min
}
//从上向下更新，左右孩子
void push_down (ll root, ll L, ll R) {
if(Lazy[root]){
Lazy[root << 1] += Lazy [root];
Lazy[root << 1 | 1] += Lazy[root];
ll mid = (L + R) >> 1;
seg_tree[root << 1] += Lazy[root] * (mid - L + 1);
seg_tree[root << 1 | 1] += Lazy[root] * (R - mid);
Lazy[root] = 0;
}
}
//建树
//[L,R]就是对应arr数组里面的数
void build (ll root, ll L, ll R) {
Lazy[root] = 0;
if(L == R) {
seg_tree[root] = arr[L];
return ;
}
ll mid = (L + R) >> 1;
build(root << 1, L, mid);
build(root << 1 | 1, mid + 1, R);
push_up(root);
}
//区间查询
//查找区间[LL,RR]的最大/小值
ll query (ll root, ll L, ll R, ll LL, ll RR) {
if (LL <= L && R <= RR) return seg_tree[root];
push_down(root, L, R); //每次访问都去检查Lazy 标记
ll Ans = -2e18;
ll mid = (L + R) >> 1;
if(LL <= mid) Ans = max(Ans, query(root << 1, L, mid, LL, RR)); //最小值改min
if(RR > mid) Ans = max(Ans, query(root << 1 | 1, mid + 1, R, LL, RR)); //最小值改min
return Ans;
}
//区间修改 +-某值
//使得区间[LL,RR]的值都加上val
void update_Interval(ll root, ll L, ll R, ll LL, ll RR, ll val){
if (LL <= L && R <= RR) {
Lazy[root] += val;
seg_tree[root] += val * (R - L + 1);
return ;
}
push_down(root, L, R);
ll mid = (L + R) >> 1;
if (LL <= mid) update_Interval(root << 1, L, mid, LL, RR, val);
if (RR > mid) update_Interval(root << 1 | 1, mid + 1, R, LL , RR, val);
push_up(root);
}
//单点修改 可以改为某值，或者+-某值
//把pos位置的值改成val
void update(ll root, ll L, ll R, ll pos, ll val) {
if(L == R){
seg_tree[root] = val; //点直接变为某值
return ;
}
ll mid = (L + R) >> 1;
if(pos <= mid) update(root << 1, L, mid, pos, val);
else update(root << 1 | 1, mid + 1, R, pos, val);
push_up(root);
}
std::vector<long long> manacher(std::string s){
std::string t = "#";
for(auto c : s){
t += c;
t += '#';
}
long long n = t.size();
std::vector<long long> r(n);
for(long long i = 0, j = 0; i < n; i++){
if(2 * j - i >= 0 && j + r[j] > i){
r[i] - std::min(r[2 * j - i], j + r[j] - i);
}
while(i - r[i] >= 0 && i + r[i] < n && t[i - r[i]] == t[i + r[i]]){
r[i] += 1;
}
if(i + r[i] > j + r[j]){
j = i;
}
}
return r;
}
//string s;
//cin >> s;
// auto rad = manacher(s);
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
long long t, n, l, r, k, flag, x, temp, last, maxx, sub, m, y;
long long summ;
string s;
cin >> n;
for (int i = 0; i < 26; i++){
cin >> v[i];
}
s.clear();
cin>>s;
arr[0] = 0;
for(int i=1;i<=n;++i){
arr[i] = arr[i-1] + v[s[i-1] -'a'];
//printf("%lld ", arr[i]);
}
//printf("\n");
build(1,1,n);
//printf("%d\n",query(1,1,n,1,r));
auto rad = manacher(s);
//for(int i = 0; i < rad.size(); i++){
//printf("%lld ", rad[i]);
//}
//printf("\n");
long long changdu;
maxx = 0;
for(int i = 0; i < rad.size(); i++){
if(i%2==1){
//you zi mu
//suan shang zi ji
changdu = rad[i]/2;
sub = (i+1)/2;
if(sub<=0||sub>n){
continue;
}
if(changdu==1){
temp = 0;
x = temp * 2 + v[s[sub-1]-'a'];
//printf("%lld %d\n", x, sub);
maxx = max(x,maxx);
continue;
}
//query(1,1,n,sub+1,sub+changdu-1) - qz[sub];
// < 0 = 0
temp = query(1,1,n,sub+1,sub+changdu-1) - arr[sub];
if(temp < 0){
temp = 0;
}
x = temp * 2 + v[s[sub-1]-'a'];
//printf("%lld %d %lld %lld %lld\n", x, sub, temp, arr[sub], query(1,1,n,sub+1,sub+changdu-1));
maxx = max(x,maxx);
}
else{
//wu zi mu
changdu = rad[i]/2;
// qian
sub = i/2;
if(sub<=0||sub>=n){
continue;
}
if(changdu==0){
//printf("000 %d\n", sub);
continue;
}
//query(1,1,n,sub+1,sub+changdu) - qz[sub];
temp = query(1,1,n,sub+1,sub+changdu) - arr[sub];
x = temp * 2;
//printf("%lld %d\n", x, sub);
maxx = max(x, maxx);
}
}
printf("%lld\n", maxx);
return 0;
}
J
不会
K
大概举几个例子找一下规律就行了，队友写的我也不太懂。
#include <bits/stdc++.h>
using namespace std;
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
long long t, n, l, r, k, flag, x, temp, last, maxx, sub, m, y;
long long summ;
int q[200005];
long long yun, yum;
cin >> t;
for(int o = 1; o <= t; o++){
cin >> n;
cin>>m;
yun = n%12;
//yun * m
yum = m%12;
//yum*n
//yun * (m-yum)
flag = 0;
temp = 0;
if(n%3==0&&n%4==0){
if(m>=3&&m!=5){
flag = 1;
}
}
else if(n%3==0){
if(m%4==0){
flag = 1;
}
}
else if(n%4==0){
if(m%3==0){
flag = 1;
}
}
else{
if(n!=5&&n>=3){
if(m%3==0&&m%4==0){
flag = 1;
}
}
}
if(flag==1){
printf("Yes\n");
}
else{
printf("No\n");
}
}
return 0;
}
L
打表发现有规律 an=4an-1-2an-2 ,矩阵快速幂加速递推即可。不过疑似因为负数取模导致矩阵快速幂写炸了没调出来。顺便markdown怎么把数组递推公式改成公式形式，这样好难受。
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define lowbit(x) ((x)&(-(x)))
#define foru(i,begin,end) for(i=begin;i<=end;i++)
#define ford(i,begin,end) for(i=begin;i>=end;i--)
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define maxheap(x) priority_queue<x,vector<x>,less<x> >
#define minheap(x) priority_queue<x,vector<x>,greater<x> >
#define endl '\n'
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
typedef long long ll;
//int128__t
typedef unsigned long long ull;
//#define mod 1000000009
#define mod 1000000007
struct juzhen
{
ll m[3][3];
juzhen operator*(juzhen b)
{
int i,j,k;
juzhen temp;
for(k=1;k<=2;k++)
{
for(i=1;i<=2;i++)
{
for(j=1;j<=2;j++)
{
temp.m[i][j]=(temp.m[i][j]%mod+m[i][k]%mod*b.m[k][j]%mod)%mod;
}
}
}
return temp;
}
juzhen()
{
m[1][1]=m[1][2]=m[2][1]=m[2][2]=0;
}
};
juzhen a;
juzhen calc(long long k)
{
juzhen temp;
int i;
for(i=1;i<=2;i++) temp.m[i][i]=1;
temp.m[1][2]=temp.m[2][1]=0;
while(k)
{
if(k&1) temp=temp*a;
a=a*a;
k/=2;
}
return temp;
}
int main()
{
int t;
cin>>t;
while(t--)
{
ll n;
cin>>n;
if(n&1||n<4)
{
cout<<0<<endl;
continue;
}
if(n==4)
{
cout<<2<<endl;
continue;
}
if(n==6)
{
cout<<8<<endl;
continue;
}
n-=3;
n=(n+1)/2;
a.m[1][1]=4,a.m[1][2]=-2,a.m[2][1]=1,a.m[2][2]=0;
juzhen ans=calc(n-2);
ll tmp=(ans.m[1][1]%mod*8ll)%mod;
tmp+=ans.m[1][2]%mod*2ll;
tmp=(tmp%mod+mod)%mod;
cout<<tmp<<endl;
}
return 0;
}
M
签到题，不多讲了。
#include <bits/stdc++.h>
using namespace std;
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
long long t, n, l, r, k, flag, x, temp, last, maxx, sub, m, y;
long long summ;
int q[200005];
cin >> t;
for(int o = 1; o <= t; o++){
cin >> n;
summ = n*(n-1)/2;
printf("%lld\n", summ);
}
return 0;
}
京公网安备 11010502036488号