2020牛客国庆集训派对题解合集

2020牛客国庆集训派对1

A

题意
给定一个长度为1e5的字符串，求从结尾开始的最长回文子串。
题解
逆序暴力枚举回文子串起点，用字符串Hash判断是否为回文子串。
时间复杂度 $O(n)$ 。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int>pii;
const int maxn=4e5+5;
const int INF=0x3f3f3f3f;
const ull p1=131ull;
int n;
int len;
char s[maxn];
ull p[maxn],h[maxn],rh[maxn];
ull getHash(int l,int r){
    return h[r]-h[l-1]*p[r-l+1];
}
ull getrHash(int l,int r){
    int l1=len-r+1;
    int r1=len-l+1;
    return rh[r1]-rh[l1-1]*p[r1-l1+1];
}
void solve(){
    len=strlen(s+1);
    p[0]=1ull;
    h[0]=0ull;
    rep(i,1,len){
        p[i]=p[i-1]*p1;
        h[i]=h[i-1]*p1+(s[i]-'a'+1);
    }
    reverse(s+1,s+len+1);
    rep(i,1,len) rh[i]=rh[i-1]*p1+(s[i]-'a'+1);
//  rep(i,1,len){
//      D(h[i]);D(rh[i]);E;
//  }
    int ans=0;
//  rep(i,1,len/2+1){
//      if(2*i<=len&&getHash(1,i)==getrHash(i+1,2*i)) ans=max(ans,2*i);
//      if(2*i-1<=len&&getHash(1,i)==getrHash(i,2*i-1)) ans=max(ans,2*i-1);
//  }
    rrep(i,len,len/2-1){
        if(2*i-len>=1&&getHash(i,len)==getrHash(2*i-len,i)) ans=max(ans,2*len-2*i+1);
        if(2*i-len-1>=1&&getHash(i,len)==getrHash(2*i-len-1,i-1)) ans=max(ans,2*len-2*i+2);
    }
    cout<<len-ans;
}
int main() {
//  ios::sync_with_stdio(false);
//  freopen("A.in","r",stdin);
    scanf("%d%s",&n,s+1);
    solve(); 
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

B

题意
给定一个长度为1e5的序列a，求 $\sum_{i=1}^{n}\sum_{j=i}^{n}gcd(a_i,...,a_j)*max(a_i,...,a_j)$
题解
考虑每个 $a_i$ 作为区间最值的贡献，则根据辗转相除法的时间复杂度，在 $1$ 到 $i$ 中与 $a_i$ 的最大公约数至多有 $log(i)$ 个。
因此可以从左到右依次将每个 $a_i$ 作为区间的右端点，然后将其作为最大值的区间（这个区间可以用一个单调递减的单调栈维护）的最大值更新为 $a_i$ （这一步可以用线段树区间修改）。接下来，只要从 $i$ 位置不断向前二分的找出每一段最大公约数相同的区间（静态维护区间最大公约数可以用ST实现），累计贡献即可。
时间复杂度 $O(n(logn)^2)$ 。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=2e5+5;
const int maxlogn=20;
const int INF=0x3f3f3f3f;
const int mod=1000000007;
int n;
int a[maxn];
struct SegmentTree{
    int l,r;
    int v,tag;
}tr[maxn<<2];
template <typename T>
inline void read(T &x) {
    x = 0; T f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -1;
    for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
    x *= f;
}
template <typename T>
inline void w(T x) { if (x > 9) w(x / 10); putchar(x % 10 + 48); }
template <typename T>
inline void write(T x, char c) { if(x < 0) putchar('-'), x = -x;w(x); putchar(c); }
inline void spread(int rt){
    if(!tr[rt].tag) return;
    tr[rt<<1].tag=tr[rt<<1|1].tag=tr[rt].tag;
    tr[rt<<1].v=1ll*tr[rt].tag*(tr[rt<<1].r-tr[rt<<1].l+1)%mod;
    tr[rt<<1|1].v=1ll*tr[rt].tag*(tr[rt<<1|1].r-tr[rt<<1|1].l+1)%mod;
    tr[rt].tag=0;
}
inline void pushup(int rt){
    tr[rt].v=(tr[rt<<1].v+tr[rt<<1|1].v)%mod;
}
void build(int rt,int l,int r){
    tr[rt].l=l,tr[rt].r=r;
    if(l==r) return;
    int mid=l+r>>1;
    build(rt<<1,l,mid),build(rt<<1|1,mid+1,r);
}
inline void update(int rt,int l,int r,int v){
    if(tr[rt].l>=l&&tr[rt].r<=r) {tr[rt].v=1ll*v*(tr[rt].r-tr[rt].l+1)%mod;tr[rt].tag=v;return;}
    spread(rt);
    int mid=tr[rt].l+tr[rt].r>>1;
    if(mid>=l) update(rt<<1,l,r,v);
    if(mid<r) update(rt<<1|1,l,r,v);
    pushup(rt);
}
inline int ask(int rt,int l,int r){
    if(tr[rt].l>=l&&tr[rt].r<=r) return tr[rt].v;
    spread(rt);
    int ans=0;
    int mid=tr[rt].l+tr[rt].r>>1;
    if(mid>=l) ans=(ans+ask(rt<<1,l,r))%mod;
    if(mid<r) ans=(ans+ask(rt<<1|1,l,r))%mod;
    return ans;
}
int lans[maxn],top,stk[maxn];
int lg[maxn],f[maxn][maxlogn];
inline int gcd(int a,int b){
    return !b?a:gcd(b,a%b);
}
void init(){
    top=0,lg[1]=0;
    rep(i,2,n) lg[i]=lg[i>>1]+1;
    int t=log2(n/2)+1;
    rep(i,1,n) f[i][0]=a[i];
    rep(j,1,t) rep(i,1,n-(1<<j)+1) f[i][j]=gcd(f[i][j-1],f[i+(1<<j-1)][j-1]);
    rep(i,1,n){
        while(top&&a[stk[top]]<a[i]) top--;
        lans[i]=(!top?0:stk[top])+1;
        stk[++top]=i;
    }
}
inline int query(int l,int r){
    int t=lg[r-l+1];
    return gcd(f[l][t],f[r-(1<<t)+1][t]);
}
int ans=0;
inline void work(int x,int ups){
    if(x<=0) return;
    int l=1,r=x;
    int stdd=query(x,ups);
    while(l<r){
        int mid=l+r>>1;
//      if(query(mid,x)==stdd) r=mid;
        if(query(mid,ups)==stdd) r=mid;
        else l=mid+1;
    }
    ans=(ans+1ll*stdd*ask(1,l,x))%mod;
    work(l-1,ups);
}
void solve(){
    init();
    build(1,1,n);
    rep(i,1,n){
        update(1,lans[i],i,a[i]);
        work(i,i);
    }
    write(ans,'\n');
}
int main() {
//  ios::sync_with_stdio(false);
//  freopen("B.in","r",stdin);
    read(n);
    rep(i,1,n) read(a[i]);
    solve();
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

C

题意
给定一棵1e5个点的树，每次可以切出一条链并接到另一个节点上。求将其转化为链的最少次数。
题解
结论题，统计这棵无根树所有度数大于2的节点树即可。
时间复杂度 $O(n)$ 。
代码如下

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=1e6;
int a[maxn],n;
long long ans;
int main()
{
    int x,y;
    cin>>n;
    for(int i=1;i<n;i++){
        cin>>x>>y;
        a[x]++;a[y]++;
    }
    for(int i=1;i<=n;i++){
        if(a[i]>2){
            ans+=a[i]-2;
        }
    }
    cout<<ans;
    return 0;
}

D

题意
在二维平面上有一条直线和1e5个点，求在这个直线上找到一个点做一个半径为R的圆，最多能覆盖多少个点。
题解
逆向考虑，以每个点做半径为R的圆，则每个点对应的圆，在直线上对应一段有向区间。于是题目转化为在直线上找到一个点，使得包含它的区间尽量多。
这个问题，可以将区间左右端点的贡献分别标记为1和-1，然后将所有区间端点排序后，扫描一遍累加贡献即可。
时间复杂度 $O(nlogn)$ 。
代码如下

#define method_2

#ifdef method_1

#endif
#ifdef method_2
/*
100% accepted
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
const int maxn=+5;
const int INF=0x3f3f3f3f;
using namespace std;
#define pii pair<double,long long>
long long n;
double R,A,B;
const int N = 2e6 + 100;
struct Node {
    double x,y;
} a[N];
vector<pii> v;
bool pd(int i) {
    double l = -B,r = A;
    double clac = l * a[i].y - a[i].x * r;
    return clac < 0;
}
int main() {
//  freopen("D.in","r",stdin);
    scanf("%lld%lf%lf%lf",&n,&R,&A,&B);
    for(int i = 1; i <= n; i++) {
        scanf("%lf%lf",&a[i].x,&a[i].y);
        double X = a[i].x * a[i].x + a[i].y * a[i].y;
        double Y = A * A + B * B;
        double I = (B * a[i].x - A * a[i].y) * (B * a[i].x - A * a[i].y);
        if(I - R * R * Y > 1e-8) continue;
        double len1 = ((pd(i))?-1:1)*sqrt(X - I / Y) - ((R * R - I / Y)>1e-8 ? sqrt(R * R - I / Y) : 0.0);
        double len2 = ((pd(i))?-1:1)*sqrt(X - I / Y) + ((R * R - I / Y)>1e-8 ? sqrt(R * R - I / Y) : 0.0);
        v.push_back(pii(len1,-1));
        v.push_back(pii(len2,1));
    }
    sort(v.begin(),v.end());
    int ans = 0,last = 0;
    rep0(i,0,v.size()) {
        last -= v[i].second;
        ans = max(ans,last);
    }
    cout << ans << endl;
    return 0;
}
#endif

E

题意
给定 $l,r（l,r<=1e12)$ ，求 $[l,r]$ 上所有数字的约数个数和。
题解
结论题，答案即为 $\sum_{i=1}^{r}{ \left\lfloor n/i \right \rfloor}-\sum_{i=1}^{l-1}{ \left\lfloor n/i \right \rfloor}$ 。该式可以使用整除分块优化。
时间复杂度 $O(\sqrt{n})$ 。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=15+5;
const int INF=0x3f3f3f3f;
ll solve(ll n) {
    ll ans=0ll;
    for(ll l=1,r; l<=n; l=r+1) {
        r=n/(n/l);
        ans+=(r-l+1)*(n/l);
    }
    return ans;
}
int main() {
//  ios::sync_with_stdio(false);
//  freopen("E.in","r",stdin);
    ll n,m;
    cin>>n>>m;
    cout<<solve(m)-solve(n-1);
    return 0;
}
#endif
#ifdef method_2

#endif
#ifdef method_3
/*

*/

#endif

F

题意
给定1e5个数，从中找出K个，使得它们的按位与的结果最大。
题解
位运算的特点是每一位相互独立，于是可以考虑从最高位向最低位贪心。即每一位如果有不小于K个数字在这一位的值为1，那么这一位就可以为1。
时间复杂度 $O(nlogn)$ 。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=2e5+5;
const int maxlogn=32;
const int INF=0x3f3f3f3f;
int n,k,a[maxn];
vector<int>v,tmp;
void solve(){
    int ans=0;
    rrep(j,maxlogn-1,0){
        int cnt=0;
        tmp.clear();
        rep0(i,0,v.size()) if(v[i]&(1<<j)) cnt++,tmp.push_back(v[i]);
        if(cnt>=k){
            ans+=(1<<j);
            v.clear();
            rep0(i,0,tmp.size()) v.push_back(tmp[i]);
        }
    }
    printf("%d",ans);
}
int main() {
//  ios::sync_with_stdio(false);
//  freopen("F.in","r",stdin);
    scanf("%d%d",&n,&k);
    rep(i,1,n) scanf("%d",&a[i]),v.push_back(a[i]);
    solve();
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

G

题意
给定100个长度和为100的禁止字符串，要求构造一个长度为1e5的字符串不包含禁止字符串，求构造方案数。
题解
将所有禁止字符串插入AC自动机，于是没有被AC自动机匹配到的字符串结尾都为合法转移。所有转移方式可以构成一个矩阵，则该矩阵的n次方，即为最终存储方案数的矩阵。求矩阵的n次方可采用矩阵快速幂优化。
时间复杂度 $O(100^3logn)$ 。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=5e5+5;
const int maxm=200+5;
const int INF=0x3f3f3f3f;
const int mod=1000000007;
int n,m;
int ch[maxn][26],vis[maxn],fail[maxn],size=0;
char S[maxn];
struct mat{
    int s[maxm][maxm];
    void clear(){memset(s,0,sizeof(s));}
    mat operator*(const mat x)const{
        mat z;z.clear();
        rep(i,0,size) rep(j,0,size) rep(k,0,size) z.s[i][j]=(1ll*s[i][k]*x.s[k][j]%mod+z.s[i][j])%mod;
        return z;
    } 
}ans,base;
queue<int>q;
void solve(){
    rep0(i,0,26) if(ch[0][i]) q.push(ch[0][i]);
    while(q.size()){
        int x=q.front();q.pop();
        rep0(i,0,26){
            int y=ch[x][i];
            if(y) fail[y]=ch[fail[x]][i],vis[y]|=vis[fail[y]],q.push(y); 
            else ch[x][i]=ch[fail[x]][i];
        } 
    }
    ans.clear();base.clear();
    rep(i,0,size) ans.s[i][i]=1;
    rep(i,0,size) rep0(j,0,26){
        if(vis[i]||vis[ch[i][j]]) continue;
        base.s[i][ch[i][j]]+=1;
//      D(i);D(j);E;
    }
    for(;n;n>>=1,base=base*base) if(n&1) ans=ans*base;
    rep(i,1,size) ans.s[0][i]=(ans.s[0][i]+ans.s[0][i-1])%mod;
    printf("%d",ans.s[0][size]); 
}
int main() {
//  ios::sync_with_stdio(false);
//  freopen("G.in","r",stdin);
    scanf("%d%d",&n,&m);
    while(m--){
        int len,u=0;
        scanf("%d%s",&len,S);
        rep0(i,0,len){
            int c=S[i]-'a';
//          D(c);E;
            if(!ch[u][c]) ch[u][c]=++size;
            u=ch[u][c];
        }
        vis[u]|=1;
    }
    solve();
    return 0;
}
#endif
#ifdef method_2
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
const int N = 5e5 + 100,mod = 1e9 + 7;
int ch[N][26],vis[N],fail[N],n,m,size;
char S[N];
struct matrix {
    int s[210][210];
    void clear() {memset(s,0,sizeof(s));}
    matrix operator *(const matrix x) const {
        matrix z;z.clear();
        for(int i = 0;i <= size;i++) {
            for(int j = 0;j <= size;j++) {
                for(int k = 0;k <= size;k++) {
                    z.s[i][j] = (z.s[i][j] + (1LL * s[i][k] * x.s[k][j] % mod)) % mod;
                }
            }
        }
        return z;
    }
}ans,base;
int main() {
    freopen("G.in","r",stdin);
    scanf("%d%d",&n,&m);
    while(m--) {
        int len,u = 0;scanf("%d%s",&len,S+1);
        for(int i = 1;i <= len;i++) {
            int c = S[i] - 'a';
            if(!ch[u][c]) ch[u][c] = ++size;
            u = ch[u][c];
        }vis[u] |= 1;
    }
    queue<int> Q;for(int i = 0;i < 26;i++) if(ch[0][i]) Q.push(ch[0][i]);
    while(!Q.empty()) {
        int u = Q.front();Q.pop();for(int i = 0;i < 26;i++) {
            int v = ch[u][i];if(v) {
                fail[v] = ch[fail[u]][i];vis[v] |= vis[fail[v]];Q.push(v);
            }
            else ch[u][i] = ch[fail[u]][i];
        }
    }
    ans.clear();base.clear();
    for(int i = 0;i <= size;i++) ans.s[i][i] = 1;
    for(int i = 0;i <= size;i++) {
        for(int j = 0;j < 26;j++) {
            if(vis[i] || vis[ch[i][j]]) continue;
            base.s[i][ch[i][j]] += 1;
            D(i);D(j);E;
        }
    }
    for(;n;n>>=1,base = base * base) if(n&1) ans = ans * base;
    for(int i = 1;i <= size;i++) ans.s[0][i] = (ans.s[0][i] + ans.s[0][i-1]) % mod;
    cout << ans.s[0][size] << endl;
    return 0;
}
#endif
#ifdef method_3
/*

*/

#endif

H

题意
给定两个长度为1e5，且只含有ACTG四种字符的字符串。每次可以交换第一个字符串的两个字符，求将第一个字符串转化为第二个字符串的最小次数。
题解
因为字符只有四种，因此可以统计出四种字符的值。于是交换方式只有如下四种。
$a_i=b_i$ ，不需要交换。
$a_i=b_j,a_j=b_i$ ，需要一次交换。
$a_i=b_j,a_j=b_k,a_k=b_i$ ，需要两次交换。
最后一种至多需要三次交换。
时间复杂度 $O(n)$ 。
代码如下

#include<iostream>
#include<cstdio>
#include<algorithm> 
#include<cstring>
#include<string>
#include<vector>
#include<map>
using namespace std;
int maxn=1e6+7;
string a,b;
map<char,int>m;
int sum[4][4];

int main(){
    cin>>a>>b;
    int len=a.size();
    m['A']=1;
    m['G']=2;
    m['T']=3;
    m['C']=0;
    int ans=0;
    for(int i=0;i<len;i++){
        if(m[a[i]]==m[b[i]]) continue;
        sum[m[a[i]]][m[b[i]]]++;
    }
    int mn;
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            mn=min(sum[i][j],sum[j][i]);
            sum[i][j]-=mn;
            sum[j][i]-=mn;
            ans+=mn;
        }
    }
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            for(int k=0;k<4;k++){
                mn=min(sum[i][j],min(sum[j][k],sum[k][i]));
                sum[i][j]-=mn;
                sum[j][k]-=mn;
                sum[k][i]-=mn;
                ans+=mn*2;
            }
        }
    }
    for(int i=0;i<4;i++) ans+=sum[i][3]*3;
    cout<<ans;
}

I

题意
给定一个1e5个点的无向图，共有1e5次询问，每次给出一组点集，求该点集构成的联通块数量。数据保证所有询问点集的总点数不超过1e5。
题解
题解链接
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1e5+5;
const int S=400; //sqrt(n)
const int INF=0x3f3f3f3f;
int n,e,p;
int u[maxn],v[maxn];
int a[maxn],vis[maxn];
vector<int>g[maxn];
int du[maxn];
int f[maxn];
int find(int x){
    return f[x]==x?x:f[x]=find(f[x]);
}
void solve(){
    rep(i,1,e){
        if(du[u[i]]<=S) g[u[i]].push_back(v[i]);
        if(du[v[i]]<=S) g[v[i]].push_back(u[i]);
        if(du[u[i]]>S&&du[v[i]]>S) g[u[i]].push_back(v[i]),g[v[i]].push_back(u[i]);
    }
    rep(i,1,n) f[i]=i;
    while(p--){
        int k;
        scanf("%d",&k);
        rep(i,1,k) scanf("%d",&a[i]),vis[a[i]]=1;
        int ans=k;
        rep(i,1,k){
            int x=find(a[i]);
            rep0(j,0,g[a[i]].size()){       
                int y=g[a[i]][j];
                if(!vis[y]) continue;
//              D(a[i]);D(y);E;
                y=find(g[a[i]][j]);
                if(x!=y) f[y]=x,ans--; //direct graph need add edge y->x, not x->y
            }
        }
        printf("%d\n",ans);
        rep(i,1,k) vis[a[i]]=0,f[a[i]]=a[i];
    }
}
int main() {
//  ios::sync_with_stdio(false);
//  freopen("I.in","r",stdin);
    scanf("%d%d%d",&n,&e,&p);
    rep(i,1,e) scanf("%d%d",&u[i],&v[i]),du[u[i]]++,du[v[i]]++;
    solve();
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

2020牛客国庆集训派对2

比赛链接

A

题意
给定一个1500个点的约瑟夫环，求最后一个存活的人的编号。
题解
刘汝佳《算法竞赛入门经典训练指南》上有关于本题的递推，不再赘述。
时间复杂度 $O(n)$ 。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1500+5;
const int INF=0x3f3f3f3f;
int n,m;
int f[maxn];
void solve(){
    memset(f,0,sizeof(f));
    f[1]=0;
    rep(i,2,n) f[i]=(f[i-1]+m)%i;
    int ans=(f[n]+1)%n;
    if(ans<=0) ans+=n;
    cout<<ans<<endl; 
}
int main() {
//  ios::sync_with_stdio(false);
//  freopen("A.in","r",stdin);
    while(cin>>n>>m){
        if(!n&&!m) break;
        solve();
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

B

题意
给定一个1e5个点的无向图，有18条有向路径。求这些路径首尾依次连接的最短长度。
题解
因为只关心每条路径起点和终点，因此首先求出所有路径起点终点之间的最短路。于是剩下的18条路径是否经过的情况可以使用一个二进制数表示，继而想到使用状压DP求解。
具体转移方程可参考哈密顿路。
时间复杂度 $O(nlogn+n2^k)$ 。
代码如下

/*

*/
#define method_2
#ifdef method_1
/*

*/

#endif
/*
attention that 
in long long
INF should be 1e18
not 0x3f3f3f3f3f3f3f3f
this error make me sumbit for more than 20 times
*/
#ifdef method_2
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<ll,int>pii;
const int maxn=1e4+5;
const int maxm=2e4+5;
const int maxk=20;
const ll INF=1e18;
int n,m,k;
int tot=1,head[maxn];
struct node{
    int from,to;
    ll w;
}edge[maxm];
ll G[maxk][maxk];
void add(int from,int to,ll w){
    edge[++tot].from=head[from],head[from]=tot,edge[tot].to=to,edge[tot].w=w;
}
int v[maxn];
ll d[maxn];
priority_queue<pii>q;
void dijkstra(int s){
//  memset(d,INF,sizeof(d));
    rep(i,1,n) d[i]=INF;
    memset(v,0,sizeof(v));
    while(q.size()) q.pop();
    d[s]=0ll;
    q.push(make_pair(0ll,s));
    while(q.size()){
        int x=q.top().second;q.pop();
        if(v[x]) continue;
        v[x]=1;
        for(int i=head[x];i;i=edge[i].from){
            int y=edge[i].to;ll w=edge[i].w;
            if(d[y]>d[x]+w){
                d[y]=d[x]+w;
                q.push(make_pair(-d[y],y));
            }
        }
    }
}

int f[maxk],t[maxk];
ll g[maxk][1<<maxk]; 
void dp(){
    rep(i,0,k) rep(j,0,(1<<k)) g[i][j]=INF;
    rep(i,1,k){
        g[i][1<<i-1]=G[i][i];       
//      D(G[i][i]);E; 
    }
    /*
    rep0(j,0,1<<k){
        rep(i,1,k){
            if((j&(1<<i-1))==0) continue;
            rep(lst,1,k){
                if(lst==i) continue;
                if((j&(1<<lst-1))==0) continue;
                g[i-1][j]=min(g[i-1][j],g[lst-1][j&(~(1<<i-1))]+G[i][lst]+G[i][i]);
            }
        }
    }
    */
    rep0(j,0,(1<<k)){
        rep(i,1,k){
            if((j&(1<<i-1))==0) continue;
            rep(lst,1,k){
                if((j&(1<<lst-1))) continue;
                g[lst][j|(1<<lst-1)]=min(g[lst][j|(1<<lst-1)],g[i][j]+G[i][lst]+G[lst][lst]);
            }
        }
    }
    ll ans=INF;
    rep(i,1,k) ans=min(ans,g[i][(1<<k)-1]);
    if(ans!=INF) printf("%lld",ans);
    else printf("-1");
}
void solve(){
    memset(G,INF,sizeof(G));
    rep(i,1,k){
        dijkstra(f[i]);
        rep(j,1,k) G[i][j]=d[t[j]]; 
    }
    dp();   
}
int main() {
//  ios::sync_with_stdio(false);
//  freopen("B.in","r",stdin);
    scanf("%d%d%d",&n,&m,&k);
    int from,to;
    ll w;
    rep(i,1,m) scanf("%d%d%lld",&from,&to,&w),add(from,to,w),add(to,from,w);
    rep(i,1,k) scanf("%d%d",&f[i],&t[i]);
    solve(); 
    return 0;
}
#endif
#ifdef method_3
/*

*/

#endif

C

题意
给定 $1$ 到 $76$ 个数字，求存在多少个极大子集，满足其中任意两个数不相邻。
题解
DFS模板题。
时间复杂度 $O(2^{n/3})$ 。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=+5;
const int INF=0x3f3f3f3f;
int f[]={0,0,0,1,3,4,5,7,9,12,16,21,28,37,49,65,86,114,151,200,265,351,465,616,816,1081,1432,1897,2513,3329,4410,5842,7739,10252,13581,17991,23833,31572,41824,55405,73396,97229,128801,170625,226030,299426,396655,525456,696081,922111,1221537,1618192,2143648,2839729,3761840,4983377,6601569,8745217,11584946,15346786,20330163,26931732,35676949,47261895,62608681,82938844,109870576,145547525,192809420,255418101,338356945,448227521,593775046,786584466,1042002567,1380359512,1828587033};
int n;
ll dfs(int x){
    if(x>n) return 0;
    if(x==n||x==n-1) return 1;
    ll res=0;
    res+=dfs(x+2)+dfs(x+3);
    return res;
}
void solve(){
    ll ans=0ll;
    ans+=dfs(1)+dfs(2);
    printf("%lld,",ans);
}
int main() {
//  ios::sync_with_stdio(false);
//  freopen("C.in","r",stdin);
//  freopen("C.out","w",stdout);
//  rep(i,4,76) n=i,solve();
    int kase=0;
    while(cin>>n&&n) cout<<"Case #"<<++kase<<": "<<f[n]<<endl;
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

D

题意
求MST。
题解
时间复杂度 $O(nlogn)$ 。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
mst模板题。 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100+5;
const int INF=0x3f3f3f3f;
int n,tot,ans,f[maxn],m;
struct node{
    int from,to,c;
    bool operator<(const node& h)const{return c<h.c;}
}edge[maxn*maxn];
void add(int from,int to,int c){
    edge[++tot].from=from,edge[tot].to=to,edge[tot].c=c;
}
void init(){
    tot=0,ans=0;
    for(int i=1;i<=n;i++) f[i]=i;
}
int find(int x){
    return f[x]==x?x:f[x]=find(f[x]);
}
void kruskal(){
    sort(edge+1,edge+m+1);
    int cnt=0; 
    rep(i,1,m){
        if(cnt>=n-1) break;
        int x=edge[i].from,y=edge[i].to,c=edge[i].c;
        x=find(x),y=find(y);
        if(x!=y){
            f[x]=y;ans+=c;cnt++;
        }
    }
}
int main() {
//  freopen("D.in","r",stdin);
    int T;
    cin>>T;
    rep(kase,1,T){
        printf("Case #%d: ",kase);
        cin>>n>>m;
        init();
        int from,to,temp;
        rep(i,1,m) cin>>from>>to>>temp,add(from,to,temp);
        kruskal();
        printf("%d meters\n",ans);
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

E

题意
模拟矩阵乘法。
题解
时间复杂度 $O(n^3)$ 。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=20+5;
const int INF=0x3f3f3f3f;
int n,m,p,q;
ll a[maxn][maxn],b[maxn][maxn],c[maxn][maxn];
void mul(){
    rep(i,1,m) rep(j,1,q) rep(k,1,n) c[i][j]+=a[i][k]*b[k][j];
}
void solve(){
    memset(c,0,sizeof(c));
    if(n!=p) {printf("undefined\n");return;}
    mul();
    rep(i,1,m){
        printf("| ");
        rep(j,1,q) printf("%lld ",c[i][j]);
        printf("|\n");
    }
}
int main() {
//  ios::sync_with_stdio(false);
//  freopen("E.in","r",stdin);
    int kase=0;
    while(scanf("%d%d%d%d",&m,&n,&p,&q)==4&&m&&n&&p&&q){
        printf("Case #%d:\n",++kase);
        rep(i,1,m) rep(j,1,n) scanf("%lld",&a[i][j]);
        rep(i,1,p) rep(j,1,q) scanf("%lld",&b[i][j]);
        solve();
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

F

题意
求下面代码的结果。 $n<=max \; long \; long$

sum = 0 
for r1 = 0 to N-1     
    for c1 = 0 to N-1         
        for r2 = r1+1 to N             
            for c2 = r2+1 to N                 
                sum = sum + (r2-r1)*(c2-c1) 
print(sum)

题解
打表找规律即可。
时间复杂度 $O(1)$ 。
代码如下

T=int(input())
while T>0:
    T=T-1
    ans=int(1)
    n=int(input())
    ans*=int(n*(n+1)*(n+2)/6)
    ans*=ans
    print(ans)

G

题意
模拟题。
题解
时间复杂度 $O(n)$ 。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=+5;
const int INF=0x3f3f3f3f;
int n;
void solve(){
    double res=0.0;
    rep(i,1,n){
        double c,b,l,nasi;
        double sum=0.0;
        cin>>c>>b>>l>>nasi;
        sum+=c+b+l;
        res-=8.0*sum/85.0;
        res+=nasi*0.6;
        res+=0.8*c+1.0*b+1.2*l;
        res-=c*7.5/85.0+b*24.0/85.0+l*32.0/85.0; 
    }
    printf("RM%.2lf\n",res);
}
int main() {
//  ios::sync_with_stdio(false);
//  freopen("G.in","r",stdin);
    int kase=0;
    while(cin>>n&&n) cout<<"Case #"<<++kase<<": ",solve();
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

J

题意
求斐波那契的第n项。
题解
模拟即可，注意加入高精度。
时间复杂度 $O(n)$ 。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=+5;
const int INF=0x3f3f3f3f;
const int MAXN = 550;
const int MAXNLEN = 130;
int F[MAXN][MAXNLEN];
char Fi[MAXN][MAXNLEN],ans[MAXN];
void Fibo() {
    F[1][0] = 1;
    F[2][0] = 1;
    for(int i = 3; i <= 500; ++i) {
        for(int j = 0; j <= 110; ++j) {
            F[i][j] = F[i][j] + F[i-1][j] + F[i-2][j];
            if(F[i][j] >= 10) {
                F[i][j+1] += F[i][j]/10;
                F[i][j] %= 10;
            }
        }
    }
    for(int i = 1; i <= 500; ++i) {
        int j;
        for(j = 110; j >= 0; j--)
            if(F[i][j] == 0)
                continue;
            else
                break;
        int k = 0;
        for(; j >= 0; j--)
            Fi[i][k++] = F[i][j] + '0';
        F[i][k] = '\0';
    }
}
void solve() {
    Fibo();
    int x; 
    while(cin>>x){
        if(x==-1) break;
        printf("Hour: %d: %s cow(s) affected\n",x,Fi[x]); 
    }
}
int main() {
//  ios::sync_with_stdio(false);
//  freopen("J.in","r",stdin);
    solve();
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

2020牛客国庆集训派对3

比赛链接

B

题意
给定一个200个点，400条边的无向图，第i条边的边权为 $x_i+a*y_i$ ， $a$ 为 $[0,1]$ 之间随机分布的常数，求起点到终点的最短路的期望。（误差小于1e-4）
题解
因为误差范围较小，可以将 $[0,1]$ 分成1e-4份，每次求一遍最短路，累加后再除以1e-4即可。
时间复杂度 $O(1e4mlogn)$ 。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<double,int>pii;
const int maxn=200+5;
const int maxm=400+5;
const int INF=0x3f3f3f3f;
int n,m,s,t; 
double d[maxn];
int vis[maxn];
struct node{
    int v,x,y;
    node(){}
    node(int _v,double _x,double _y){v=_v,x=_x,y=_y;}
};
vector<node>g[maxn];
priority_queue<pii>q;
void init(){
    while(q.size()) q.pop();
    rep(i,1,n) d[i]=1e18;
    memset(vis,0,sizeof(vis)); 
}
double dij(double a){
    init();
    d[s]=0.0;
    q.push(make_pair(0.0,s));
    while(q.size()){
        int x=q.top().second;q.pop();
        if(vis[x]) continue;
        vis[x]=1;
        rep0(i,0,g[x].size()){
            int y=g[x][i].v;
            double w1=g[x][i].x,w2=g[x][i].y;
            if(d[y]>d[x]+w1+w2*a){
                d[y]=d[x]+w1+w2*a;
                q.push(make_pair(-d[y],y));
            }
        }
    }
    return d[t];
}
void solve(){
    int T=100000;
    double ans=0.0;
    rep(i,0,T) ans+=dij(1.0*i/T);
    printf("%.6lf",ans/(1.0*T));
}
int main() {
//  ios::sync_with_stdio(false);
//  freopen("B.in","r",stdin);
    scanf("%d%d%d%d",&n,&m,&s,&t);
    int u,v;
    double x,y;
    rep(i,1,m) scanf("%d%d%lf%lf",&u,&v,&x,&y),g[u].push_back(node(v,x,y)),g[v].push_back(node(u,x,y));
    solve();
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

D

题意
给定两个内切圆和1e4个位于两圆中间的点，求一个同时内切于这两个圆的圆，使得覆盖的点最多。
题解
两个内切圆反演后得到的是两条直线，而点的反演在两条直线之间，所求圆反演后的圆心处于这两条直线的中线上。于是可以转化为这题的做法。
时间复杂度 $O(nlogn)$ 。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1e4+5;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
int T;
int n;
double R,r;
struct node{
    double x,y;
    node(){}
    node(double _x,double _y){x=_x,y=_y;} 
}p[maxn];
vector<node>v;
inline double sqr(double x){return x*x;}
int sgn(double x){
    if(fabs(x)<eps) return 0;
    if(x>0) return 1;
    return -1;
}
bool cmp(node a,node b){
    if(sgn(a.y-b.y)==0) return a.x>b.x; //1 is before -1 , considering there maybe more than two points appear at same position
    return a.y<b.y;
}
void init(){
    v.clear();
}
void solve(){
    init();
    double mid=(double)R+(double)(R*R)/(double)r;
    double rr=(double)(R*R)/(double)r-(double)R;
    rep(i,1,n){
        ll x,y;
        cin>>x>>y;
        p[i].x=(double)(4ll*R*R*x)/(double)(x*x+y*y);
        p[i].y=(double)(4ll*R*R*y)/(double)(x*x+y*y);
        //点的反演
        if(sgn(fabs(p[i].x-mid)-rr)==0){
            v.push_back(node(1.0,p[i].y));
            v.push_back(node(-1.0,p[i].y));
        }
        else if(sgn(fabs(p[i].x-mid)-rr)<0){
            double h=sqrt(sqr(rr)-sqr(p[i].x-mid));
            v.push_back(node(-1.0,p[i].y+h));
            v.push_back(node(1, p[i].y-h));
        }
        else continue;
    }
    sort(v.begin(),v.end(),cmp);    
    int ans=0,cnt=0;
    rep0(i,0,v.size()) cnt+=v[i].x,ans=max(ans,cnt);
    printf("%d\n",ans);
}
int main() {
//  ios::sync_with_stdio(false);
//  freopen("D.in","r",stdin);
    scanf("%d",&T);
    while(T--){
        scanf("%d%lf%lf",&n,&R,&r);
        solve();
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

F

题意
求一棵无根树中度数为1的节点数。
题解
模拟即可。
时间复杂度 $O(n)$ 。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1e5+5;
const int INF=0x3f3f3f3f;
int n;
int x,y;
int v[maxn];
void solve(){
    rep(i,1,n-1) scanf("%d%d",&x,&y),v[x]++,v[y]++;
    int ans=0;
    rep(i,1,n) if(v[i]==1) ans++;
    printf("%d",ans);
}
int main() {
//  ios::sync_with_stdio(false);
//  freopen("F.in","r",stdin);
    scanf("%d",&n);
    solve();
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

J

题意
给定一个长度为1e5的序列，每次可以选择其中 $m$ 个数字，将他们全体减一。求最多能进行多少次操作。
题解
考虑二分答案 $mid$ ，对于大于等于 $mid$ 的数字，可以分配到 $m$ 组里，贡献即为 $mid$ 。对于小于 $mid$ 的数字，则必须全部用完，贡献即为它本身。若所有数字的贡献和不小于 $mid*m$ ，那么当前 $mid$ 即合法。
时间复杂度 $O(nlogn)$ 。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=3e5+5;
const ll INF=0x7fffffffffffffffll;
int n,m,T;
ll a[maxn],sum;
void init(){
    sum=0ll;
}
bool check(ll mid){
    ll res=0;
    rep(i,1,n) res+=min(a[i],mid);
    return res>=mid*m; 
}
void solve(){
    sort(a+1,a+n+1);
    reverse(a+1,a+n+1);
    ll l=0,r=sum/m+1;
    while(l<r){
        ll mid=l+r+1>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    printf("%lld\n",l);
}
int main() {
//  ios::sync_with_stdio(false);
//  freopen("J.in","r",stdin);
    scanf("%d",&T);
    while(T--){
        init();
        scanf("%d%d",&n,&m);
        rep(i,1,n) scanf("%lld",&a[i]),sum+=a[i];
        solve();
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

2020牛客国庆集训派对4

比赛链接

B

题意
求1e3个数字的最长等差子序列。
题解
考虑DP，设 $f[i,j]$ 表示 $[i,j]$ 的最长等差子序列（选取 $a_i$ 和 $a_j$ ）。于是存在转移方程 $f[i,j]=max(f[k,i])+1,a_k+a_j=2*a_i$ 。这样直接暴力枚举三个维度，时间复杂度过高。但注意到符合条件的 $j$ 和 $k$ 是分布在 $i$ 左右的，所以可以枚举 $i$ ，然后用两个指针往 $i$ 的两侧移动，符合条件时更新答案。
时间复杂度 $O(n^2)$ 。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=5000+5;
const int INF=0x3f3f3f3f;
int n;
int a[maxn],f[maxn][maxn];
void solve(){
    sort(a+1,a+n+1);
    rep(i,1,n) rep(j,i+1,n) f[i][j]=2;
    int ans=2;
    rep(i,2,n-1){
        int k=i-1,j=i+1;
        while(k>=1&&j<=n){
            if(a[k]+a[j]<2*a[i]) j++;
            else if(a[k]+a[j]>2*a[i]) k--;
            else{
                f[i][j]=max(f[i][j],f[k][i]+1);
                ans=max(ans,f[i][j]);
                k--,j++;
            }
        }
    }
    printf("%d",ans);
}
int main() {
//  ios::sync_with_stdio(false);
//  freopen("B.in","r",stdin);
    scanf("%d",&n);
    rep(i,1,n) scanf("%d",&a[i]);
    solve();
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

D

题意
给出两个长度为5000的 01 串a和b，求最短的 01 串 t ，使得 t 不是 a 和 b 的子序列，若有多个答案则输出字典序最小的。
题解
题解链接
代码如下

/*

*/
#define method_2
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=+5;
const int INF=0x3f3f3f3f;

void solve() {

}
int main() {
//  ios::sync_with_stdio(false);
    freopen("D.in","r",stdin);

    return 0;
}
#endif
#ifdef method_2
/*

*/
//#pragma GCC optimize(2)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
#include<list>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
const int inf=0x3f3f3f3f;
const int N=4e3+100;
char s1[N],s2[N];
int nt1[N][2],nt2[N][2],len1,len2;
int dp[N][N],path[N][N];
int dfs(int x,int y) {
    if(x==len1+1&&y==len2+1)
        return dp[x][y]=0;
    if(dp[x][y]!=-1)
        return dp[x][y];
    int ans1=dfs(nt1[x][0],nt2[y][0]); // chose 0
    int ans2=dfs(nt1[x][1],nt2[y][1]); // chose 1
    if(ans1<=ans2)
        path[x][y]=0;
    else
        path[x][y]=1;
//  D(x);D(y);D(ans1);D(ans2);E;
    return dp[x][y]=min(ans1,ans2)+1;
}
void print(int x,int y) {
    if(x==len1+1&&y==len2+1)
        return;
    putchar(path[x][y]+'0');
    print(nt1[x][path[x][y]],nt2[y][path[x][y]]);
}
void init(char s[],int &len,int nt[][2]) {
    len=strlen(s+1);
    nt[len+1][0]=nt[len+1][1]=len+1;
    nt[len][0]=nt[len][1]=len+1;
    for(int i=len-1; i>=0; i--) {
        nt[i][0]=nt[i+1][0];
        nt[i][1]=nt[i+1][1];
        nt[i][s[i+1]-'0']=i+1;
    }
}

int main() {
//  freopen("D.in","r",stdin);
    scanf("%s%s",s1+1,s2+1);
    init(s1,len1,nt1);
    init(s2,len2,nt2);
    memset(dp,-1,sizeof(dp));
    dfs(0,0);
    print(0,0);
    return 0;
}
#endif
#ifdef method_3
/*

*/

#endif

F

题意
给定长度为1e5的序列，每次可以交换两个相邻元素，求将其变成合唱队形（先升序后降序）的最小次数。
题解
考虑每次移动当前最小的数字，那么它向左向右移动到两端的次数都可以利用树状数组确定。
时间复杂度 $O(nlogn)$ 。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100000+5;
const int INF=0x3f3f3f3f;
int n,a[maxn];
int b[maxn],cnt;
int l[maxn],r[maxn];
int c[maxn];
void add(int x){
    for(;x<=cnt;x+=x&-x) c[x]++;
}
int ask(int x){
    int res=0;
    for(;x;x-=x&-x) res+=c[x];
    return res;
}
void solve(){
    sort(b+1,b+n+1);
    cnt=unique(b+1,b+n+1)-b-1;
    rep(i,1,n) a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
//  rep(i,1,n) D(a[i]);
    rep(i,1,n){
        l[i]=ask(a[i]);
        add(a[i]);
    }
//  rep(i,1,n) D(a[i]);E;
//  rep(i,1,n) D(l[i]);E;
    memset(c,0,sizeof(c));
    rrep(i,n,1){
        r[i]=ask(a[i]);
        add(a[i]);
    }
//  rep(i,1,n) D(r[i]);E;
    ll ans=0ll;
    rep(i,1,n){
        ans+=ll(min(i-1-l[i],n-i-r[i]));
    }
    printf("%lld",ans);
}
int main() {
//  ios::sync_with_stdio(false);
//  freopen("F.in","r",stdin);
    scanf("%d",&n);
    rep(i,1,n) scanf("%d",&a[i]),b[i]=a[i];
    solve();
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

H

题意
给出一棵1e5个节点的树，每个节点都有一个颜色，现在需要执行1e5次操作，每次操作分为如下两种类型：
Q x：回答所有颜色为 x 的节点构成的连通子图含有的最少边数
U x y：将点 x 的颜色修改为 y
题解
题解链接
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1e5+5;
const int maxlogn=20;
const int INF=0x3f3f3f3f;
struct node{
    int from,to;
}edge[maxn<<1];
int head[maxn],tot=1;
void add(int from,int to){
    edge[++tot].from=head[from],edge[tot].to=to,head[from]=tot;
}
int n,m,c[maxn];
int dfn[maxn],cnt=0;
struct Scmp{
    bool operator()(int x,int y) {return dfn[x]<dfn[y]; }
};
set<int,Scmp>S[maxn];
void dfs(int x,int fa){
    dfn[x]=++cnt;
    for(int i=head[x];i;i=edge[i].from){
        int y=edge[i].to;
        if(y==fa) continue;
        dfs(y,x);
    }
}
queue<int>q;
int t;
int d[maxn],f[maxn][maxlogn];
void bfs(int st){
    d[st]=1;q.push(st);
    while(q.size()){
        int x=q.front();q.pop();
        for(int i=head[x];i;i=edge[i].from){
            int y=edge[i].to;
            if(d[y]) continue;
            d[y]=d[x]+1,f[y][0]=x;
            rep(j,1,t) f[y][j]=f[f[y][j-1]][j-1];
            q.push(y);
        }
    }
//  rep(i,1,n) D(d[i]);E;
}
int lca(int x,int y){
    if(d[x]>d[y]) swap(x,y);
    rrep(i,t,0) if(d[f[y][i]]>=d[x]) y=f[y][i];
    if(x==y) return x;
    rrep(i,t,0) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
}
int dis(int x,int y){
    int res=d[x]+d[y]-2*d[lca(x,y)];
//  D(x);D(d[x]);D(y);D(d[y]);D(lca(x,y));D(res);E;
    return res;
}
int ans[maxn];
void update(int x,int flag){
    if(flag==-1) S[c[x]].erase(x);
    set<int,Scmp>::iterator it=S[c[x]].lower_bound(x),nxt,pre;
//  D(c[x]);D(x);E;
    if(S[c[x]].empty()) ans[c[x]]=0;
    else if(it==S[c[x]].begin()||it==S[c[x]].end()){
//      D(*S[c[x]].begin());D(*S[c[x]].rbegin());D(*it);E;
        ans[c[x]]+=flag*dis(*S[c[x]].begin(),x);
        ans[c[x]]+=flag*dis(*S[c[x]].rbegin(),x);
        ans[c[x]]-=flag*dis(*S[c[x]].begin(),*S[c[x]].rbegin());
//      D(ans[c[x]]);E;
    } 
    else{
        nxt=it,pre=--it;
//      D(*nxt);D(*pre);E;    
        ans[c[x]]+=flag*dis(*nxt,x);
        ans[c[x]]+=flag*dis(*pre,x);
        ans[c[x]]-=flag*dis(*pre,*nxt);
    }
    if(flag==1) S[c[x]].insert(x);
}
void solve(){
    char op[2];
    int x,y;
    while(m--){
        scanf("%s",op);
        if(op[0]=='Q'){
            scanf("%d",&x);
            if(S[x].empty()) printf("-1\n");
            else printf("%d\n",ans[x]/2);
        }
        if(op[0]=='U'){
            scanf("%d%d",&x,&y);
            update(x,-1);
            c[x]=y;
            update(x,1);
        }
    }
}
int main() {
//  ios::sync_with_stdio(false);
//  freopen("H.in","r",stdin);
    scanf("%d",&n);
    t=int(log(n)/log(2))+1;
    int from,to;
    rep(i,1,n-1) scanf("%d%d",&from,&to),add(from,to),add(to,from);
    dfs(1,-1);
    bfs(1);
    rep(i,1,n) scanf("%d",&c[i]),update(i,1);
    scanf("%d",&m);
    solve();
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

I

题意
求田忌赛马的一组字典序最大的解。（ $n<=5000$ )
题解
题解链接
代码如下

/*

*/
#define method_2
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=+5;
const int INF=0x3f3f3f3f;

void solve(){

}
int main() {
//  ios::sync_with_stdio(false);
    freopen("I.in","r",stdin);

    return 0;
}
#endif
#ifdef method_2
/*

*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#define I int
#define ll long long
#define F(i,a,b) for(I i=a;i<=b;++i)
#define Fd(i,a,b) for(I i=a;i>=b;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#define N 5010
 
using namespace std;
I rd(I &x){
    x=0;I w=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') w=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    x*=w;
}
I n,a[N],b[N],c[N],d[N],t,s,l,r,k,mid,ans,tot;
I cmp(I x,I y){return x>y;}
I check(I x,I y){
    I k=0,p=0;
    F(i,1,s){
        if(k+1==x) k++;
        if(k<s&&b[k+1]>c[i]) k++,p++;
    }
    return p+tot+y==t;
}
I main(){
//  freopen("I.in","r",stdin);
    scanf("%d",&n);
    F(i,1,n){scanf("%d",&a[i]),c[i]=-a[i];}
    sort(c+1,c+1+n);
    F(i,1,n) scanf("%d",&b[i]),c[i]=-c[i];
    sort(b+1,b+1+n,cmp);
    F(i,1,n) if(t<n&&b[t+1]>c[i]) t++;
    s=n+1;
    F(i,1,n-1){
        s--;
        F(j,1,s) if(c[j]==a[i]){c[j]=1e9;break;}
        I k=s+1;
        F(j,1,s) if(b[j]<=a[i]){k=j;break;}
        l=1,r=k-1,ans=0;
        while(l<=r){
            mid=(l+r)>>1;
            if(check(mid,1)){ans=mid,r=mid-1;}
            else l=mid+1;
        }
        if(!ans){
            l=k,r=s;
            while(l<=r){
                mid=(l+r)>>1;
                if(check(mid,0)){ans=mid,r=mid-1;}
                else l=mid+1;
            }
        }
        printf("%d ",b[ans]);
        tot+=(b[ans]>a[i]);
        F(j,ans,s-1) b[j]=b[j+1];
        F(j,1,s) if(c[j]==1e9){
            F(k,j,s-1) c[k]=c[k+1];
            break;
        }
    }
    printf("%d ",b[1]);
    return 0;
}
#endif
#ifdef method_3
/*

*/

#endif

2020牛客国庆集训派对5

比赛链接

B

题意
给定一个长度为1e5的字符串，求它有多少个子串，重新排列后可以形成回文子串。
题解
一个字符串为回文串的条件是，它的所有字符中，至多只有一个字符出现次数为奇数。因此可以考虑使用异或运算维护每个字符出现次数的奇偶性。这样从左向右扫描一遍后，对于每个前缀异或值，它出现的次数即为对答案的贡献。（因为每出现一次，就意味着从上一个位置到当前位置的子串是一个合法子串）
时间复杂度 $O(nlogn)$ 。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=3e5+5;
const int maxm=52+5;
const int INF=0x3f3f3f3f; 
int n;
char s[maxn];
inline int ID(char ch){
    if(ch>='A'&&ch<='Z') return ch-'A';
    else return ch-'a'+26;
}
map<ll,int>mp;
void solve(){
    ll res=0ll;
    mp.clear();
    mp[0]=1;
    ll sum=0;
    rep(i,1,n){
        int ch=ID(s[i]);
        sum^=(1ll<<ch);
        res+=ll(mp[sum]);
        rep0(j,0,52) res+=ll(mp[sum^(1ll<<j)]);
        mp[sum]++;
    }
    printf("%lld",res);
}
int main() {
//  ios::sync_with_stdio(false);
//  freopen("B.in","r",stdin);
    scanf("%d",&n);
    scanf("%s",s+1);
    solve();
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

H

题意
模拟题。
题解
时间复杂度 $O(n)$ 。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1000+5;
const int INF=0x3f3f3f3f;
int n;
int len;
string s,t;
vector<string>res;
bool check(){
    int len2=t.length();
    if(len!=len2) return false;
    rep0(i,0,len){
        if(s[i]!='*'&&s[i]!=t[i]) return false;
    }
    return true;
}
void solve(){
    len=s.length();
    int cnt=0;
    res.clear();
    while(n--){
        cin>>t;
        if(check()) cnt++,res.push_back(t);
    }
    cout<<cnt<<endl;
    rep0(i,0,res.size()) cout<<res[i]<<endl; 
}
int main() {
//  ios::sync_with_stdio(false);
//  freopen("H.in","r",stdin);
    cin>>s>>n;
    solve();
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

K

题意
模拟题。
题解
时间复杂度 $O(n^2)$ 。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1000+5;
const int INF=0x3f3f3f3f;
int n,m;
struct node{
    int a,b;
}c[maxn];
int get(int i,int t){
    int times=t/(c[i].b-c[i].a);
    if(times&1) return c[i].b-t%(c[i].b-c[i].a);
    return c[i].a+t%(c[i].b-c[i].a);
}
void solve(){
    int x,y,t;
    while(m--){
        scanf("%d%d%d",&x,&y,&t);
        int cnt=0;
        rep(i,1,n){
            int pos=get(i,t);
//          D(i);D(pos);E;
            if(pos>=x&&pos<=y) cnt++;
        }
        printf("%d\n",cnt);
    }
}
int main() {
//  ios::sync_with_stdio(false);
//  freopen("K.in","r",stdin);
    scanf("%d%d",&n,&m);
    rep(i,1,n) scanf("%d%d",&c[i].a,&c[i].b);
    solve();
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif