您的位置: 首页  >  IT文章  >  2019 ICPC 徐州网络赛

2019 ICPC 徐州网络赛

分类: IT文章 • 2024-04-27 08:39:34

A.00:45:42(-1) solved by zcz

队友说抄个板子好了，我看了一下板子是扩展中国剩余定理

#include<iostream>
#include<cstdio>
#include<climits>
#include<cstring>
#include<map>
#include<algorithm>
using namespace std;
#define LL long long
const int maxn=1e5+5;
int n;
LL exgcd(LL a,LL b,LL &x,LL &y){
    if(!b){x=1,y=0;return a;}
    LL re=exgcd(b,a%b,x,y),tmp=x;
    x=y,y=tmp-(a/b)*y;
    return re;
}
LL m[maxn],a[maxn];      //m为模数集，a为余数集
LL exCRT(){
    LL M=m[1],A=a[1],t,d,x,y;int i;
    for(i=2;i<=n;i++){
        d=exgcd(M,m[i],x,y);//解方程
        if((a[i]-A)%d)return -1;//无解
        x*=(a[i]-A)/d,t=m[i]/d,x=(x%t+t)%t;//求x
        A=M*x+A,M=M/d*m[i],A%=M;//日常膜一膜（划掉）模一模，防止爆
    }
    A=(A%M+M)%M;
    return A;
}

map<long long ,int> isF;




int main()
{
    long long f1=1,f2=1;

    while(f1<=1e16)
    {
        isF[f1]=1;
        long long t=f1;
        f1=f1+f2;
        f2=t;

    }


    int i,j;
    while(scanf("%d",&n)!=EOF){
        for(i=1;i<=n;i++)scanf("%lld%lld",&m[i],&a[i]);
        long long t=exCRT();
        if(t==-1)
        {
            cout<<"Tankernb!"<<endl;
            continue;
        }
        if(isF[t]==0)
        {
            cout<<"Zgxnb!"<<endl;
        }
        else
        {
            cout<<"Lbnb!"<<endl;
        }
    }
    return 0;
}
A

B.00:11:42 solved by hl

范围小的话直接并查集，这题范围比较大，所以要离散化(雾)

#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++)  
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))  
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x)  
#define Pri(x) printf("%d
", x)
#define Prl(x) printf("%lld
",x)  
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long  
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second 
typedef vector<int> VI;
int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();}
while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
const double PI = acos(-1.0);
const double eps = 1e-9;
const int maxn = 3e6 + 10;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7; 
int N,M,K;
int fa[maxn];
int Hash[maxn];
struct query{
    int op,x;
}query[maxn];
int find(int x){
    if(x == fa[x]) return x;
    return fa[x] = find(fa[x]);
}
void Union(int a,int b){
    a = find(a); b = find(b);
    fa[a] = b;
}
int main(){
    Sca2(N,M);
    int cnt = 0;
    for(int i = 1; i <= M ; i ++){
        query[i].op = read(); query[i].x = read();
        Hash[++cnt] = query[i].x;
        if(query[i].op == 1){
            Hash[++cnt] = query[i].x + 1;
        }
    }
    sort(Hash + 1,Hash + 1 + cnt);
    cnt = unique(Hash + 1,Hash + 1 + cnt) - Hash;
    for(int i = 1; i <= cnt + 1; i ++) fa[i] = i;
    Hash[cnt + 1] = -1;
    for(int i = 1; i <= M ; i ++){
        query[i].x = lower_bound(Hash + 1,Hash + 1 + cnt,query[i].x) - Hash; 
        if(query[i].op == 1){
            Union(query[i].x,query[i].x + 1);
        }else{
            Pri(Hash[find(query[i].x)]);
        }
    } 
    return 0;
}
B

C.00:12:36(-3) solved by zcz

枚举题意，枚举到和出题人心意相通为止

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;

int main()
{
    int w;
    while(cin>>w)
    {
        if(w%2==0&&w>2)
        {
            cout<<"YES"<<endl;
        }
        else
        {
            cout<<"NO"<<endl;
        }
    }
    return 0;
}
C

D.1:05:12 solved by hl

我就比较好奇，出这种题也有钱拿吗？

#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++)  
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))  
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x)  
#define Pri(x) printf("%d
", x)
#define Prl(x) printf("%lld
",x)  
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long  
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second 
typedef vector<int> VI;
int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();}
while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
const double PI = acos(-1.0);
const double eps = 1e-9;
const int maxn = 110;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7; 
int N,M,K;
string S,T;
int main(){
    cin >> T;
    Sca(N);
    while(N--){
        cin >> S;
        if(S.length() < T.length()){
            if(T.find(S) != S.npos) puts("my child!");
            else puts("oh, child!");
        }else if(S.length() > T.length()){
            if(S.find(T) != S.npos) puts("my teacher!");
            else puts("senior!");
        }else{
            if(S == T) puts("jntm!");
            else puts("friend!");
        }
    }
    return 0;
}
D

E.00:38:48 solved by hl

从后往前枚举，树状数组维护下标最大的值，树状数组下标为数的大小

#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++)  
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))  
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x)  
#define Pri(x) printf("%d
", x)
#define Prl(x) printf("%lld
",x)  
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long  
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second 
typedef vector<int> VI;
int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();}
while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
const double PI = acos(-1.0);
const double eps = 1e-9;
const int maxn = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7; 
int N,M,K,cnt;
int a[maxn],Hash[maxn];
int tree[maxn];
void add(int u,int v){
    for(;u > 0; u -= u & -u) tree[u] = max(tree[u],v);
}
int getmax(int u){
    int ans = 0;
    for(;u <= cnt ; u += u & -u) ans = max(ans,tree[u]);
    return ans;
}
int ans[maxn];
int main(){
    Sca2(N,M);
    cnt = 0;
    for(int i = 1; i <= N ; i ++){
        a[i] = Hash[++cnt] = read();
        Hash[++cnt] = a[i] + M ;
    }
    sort(Hash + 1,Hash + 1 + cnt);
    cnt = unique(Hash + 1,Hash + 1 + cnt) - Hash - 1;
    for(int i = N ; i >= 1; i --){
        int t = getmax(lower_bound(Hash + 1,Hash + 1 + cnt,a[i] + M) - Hash);
    //    cout << "bug" << i << endl;
    //    cout << lower_bound(Hash + 1,Hash + 1 + cnt,a[i] + M) - Hash << endl;
    //    cout << t << endl;
        a[i] = lower_bound(Hash + 1,Hash + 1 + cnt,a[i]) - Hash;
        if(!t) ans[i] = -1;
        else ans[i] = t - i - 1;
    //    cout << ans[i] << endl;
        add(a[i],i);
    }
    for(int i = 1; i <= N ; i ++){
        printf("%d",ans[i]);
        if(i != N) printf(" ");
    }
    return 0;
}
E

F.03:14:29 solved by hl

本场唯一做的一道非签到题，提前感谢一下出题人

题目数据范围给的很奥妙重重，5000个询问和最多为100个k的情况仿佛在暗示什么

果不其然，一个询问点最多往上数100个祖先，枚举每个祖先作为lca对这个点产生的贡献，将会产生一个数的深度的范围，这个点的贡献是他所有子树中深度不超过某个数产生的，同时减去他的祖先对他的影响，每个询问就会变成至多100个询问。

求一个dfs序，题目就转化为了多次询问一个序列中区间所有大于等于p的数的权值和，把所有询问离线出来，用树状数组解决就好了

#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++)  
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))  
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x)  
#define Pri(x) printf("%d
", x)
#define Prl(x) printf("%lld
",x)  
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long  
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second 
typedef vector<int> VI;
int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();}
while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
const double PI = acos(-1.0);
const double eps = 1e-9;
const int maxn = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7; 
int N,M,K;
LL a[maxn];
struct Edge{
    int to,next;
}edge[maxn * 2];
int head[maxn],tot;
void init(){
    for(int i = 0 ; i <= N ; i ++) head[i] = -1;
    tot = 0;
}
void add(int u,int v){
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}
int dep[maxn],p[maxn * 2],cnt,fa[maxn];
PII pos[maxn];
void dfs(int u,int la){
    pos[u].fi = ++cnt;
    p[cnt] = u;
    for(int i = head[u]; ~i; i = edge[i].next){
        int v = edge[i].to;
        if(v == la) continue;
        fa[v] = u;
        dep[v] = dep[u] + 1;
        dfs(v,u);
    }
    pos[u].se = ++cnt;
    p[cnt] = u;
}
struct Query{
    int l,r,id;
    int k,flag;
    Query(int l = 0,int r = 0,int id = 0,int k = 0,int flag = 0):l(l),r(r),id(id),k(k),flag(flag){}
}q[maxn];
int Stack[maxn];
bool cmp(Query a,Query b){
    return a.k < b.k;
}
vector<int>Q[maxn];
LL tree[maxn],ans[maxn];
void add(int u,LL v){
    for(;u < maxn; u += u & -u) tree[u] +=v ;
}
LL getsum(int u){
    LL sum = 0;
    for(;u > 0; u -= u & -u) sum += tree[u];
    return sum;
}
int main(){
    Sca(N); init(); cnt = 0;
    for(int i = 1; i <= N ; i ++) a[i] = read();
    for(int i = 1; i <= N - 1; i ++){
        int u = read(),v = read();
        add(u,v); add(v,u);
    }
    dep[1] = 0; fa[1] = -1;
    dfs(1,-1);
    Sca(M); int o = 0;
    for(int i = 1; i <= M ; i ++){
        int u,w; Sca2(u,w);
        int j,root;
        Stack[0] = u;
        for(j = 0,root = u; j < w && fa[root] != -1;){
            root = fa[root];
            Stack[++j] = root;
        }
        int Mi = -1;
        for(int k = j ;k >= 0 ; k --){
            int v = Stack[k];
            int Mx = dep[v] + w - (dep[u] - dep[v]);
            if(Mi >= Mx) continue;
            if(Mi >= 0) q[++o] = Query(pos[v].fi,pos[v].se,i,Mi,-1);
            if(Mx >= 0) q[++o] = Query(pos[v].fi,pos[v].se,i,Mx,1);
            Mi = max(Mi,Mx); 
        }
    }
    sort(q + 1,q + 1 + o,cmp);
    int f = 1;
    for(int i = 1; i <= N ; i ++){
        Q[dep[i]].pb(i);
    }
    for(int i = 0; f <= o ; i ++){
        for(int j = 0 ; j < Q[i].size(); j ++){
            int v = Q[i][j];
            add(pos[v].fi,a[v]);
        }
        while(f <= o && q[f].k == i){
            ans[q[f].id] += getsum(q[f].l - 1) * -1 * q[f].flag;
            ans[q[f].id] += getsum(q[f].r) * q[f].flag;
            f++;
        }
    }
    for(int i = 1; i <= M; i ++){
        Prl(ans[i]);
    }
    return 0;
}
F

G.00:50:53 solved by hl

回文树，bitset维护一下每个结点字母的数量直接冲就行了

不用bitset,建完树之后dfs统计也行，我寻思bitset可能会快一点，空间复杂度也顶住了

#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++)  
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))  
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x)  
#define Pri(x) printf("%d
", x)
#define Prl(x) printf("%lld
",x)  
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long  
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second 
typedef vector<int> VI;
int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();}
while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
const double PI = acos(-1.0);
const double eps = 1e-9;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7; 
int N,M,K;
const int maxn = 3e5 + 10;
const int maxc = 26;
struct Pal_T{
    int next[maxn][maxc];
    int fail[maxn],cnt[maxn],num[maxn],len[maxn],S[maxn];
    bitset<maxc>P[maxn];
    int last,n,tot;
    int newnode(int l){
        for(int i = 0 ; i < maxc; i ++) next[tot][i] = 0;
        cnt[tot] = num[tot] = 0;
        len[tot] = l;
        P[tot].reset();
        return tot++;
    }
    void init(){
        tot = 0; 
        newnode(0); //偶数根节点
        newnode(-1); //奇数根节点
        last = n = 0;
        S[n] = -1; fail[0] = 1;
    }
    int getfail(int x){
        while(S[n - len[x] - 1] != S[n]) x = fail[x];
        return x;
    }
    void add(int c){
        c -= 'a';
        S[++n] = c;
        int cur = getfail(last);
        if(!next[cur][c]){
            int now = newnode(len[cur] + 2);
            P[now] = P[cur];
            P[now][c - 'a'] = 1;
            fail[now] = next[getfail(fail[cur])][c];
            next[cur][c] = now;
            num[now] = num[fail[now]] + 1;
        }
        last = next[cur][c];
        cnt[last]++;
    }
    LL count(){
        LL ans = 0;
        for(int i = tot - 1; i >= 0; i --){
            cnt[fail[i]] += cnt[i];
            ans += 1ll * P[i].count() * cnt[i];
        } 
        return ans;
    }
}PT;
char str[maxn];
int main(){
    scanf("%s",str); PT.init();
    for(int i = 0;str[i]; i ++) PT.add(str[i]);
    Prl(PT.count());
    return 0;
}
G

I.2:01:19 solved by hl

因为原图是个全排列，可以证明即使将所有有关系的数连边，空间复杂度也是nlogn

这就变成了一个区间查询内部包含多少线段的问题了,简单的二位偏序问题，只要把E题敲完的树状数组复制过来就可以了

#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++)  
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))  
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x)  
#define Pri(x) printf("%d
", x)
#define Prl(x) printf("%lld
",x)  
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long  
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second 
typedef vector<int> VI;
int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();}
while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
const double PI = acos(-1.0);
const double eps = 1e-9;
const int maxn = 1e5 + 10;
const int maxm = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7; 
int N,M,K;
int a[maxn],id[maxn];
struct Line{
    int l,r;
    Line(int l = 0,int r = 0):l(l),r(r){}
}line[maxm];
struct Query{
    int l,r,id;
}q[maxn];
bool cmp(Query a,Query b){
    return a.r < b.r;
}
bool cmp2(Line a,Line b){
    return a.r < b.r;
}
int tree[maxn];
void add(int u,int v){
    for(;u > 0; u -= u & -u) tree[u] += v;
}
int getsum(int u){
    int ans = 0;
    for(;u < N; u += u & -u) ans += tree[u];
    return ans;
}
int ans[maxn];
int main(){
    Sca2(N,M);
    for(int i = 1; i <= N; i ++){
        a[i] = read(); id[a[i]] = i;
    }
    int cnt = 0;
    for(int i = 1; i <= N ; i ++){
        for(int j = i + i ; j <= N ; j += i){
            line[++cnt] = Line(id[i],id[j]);
            if(line[cnt].l > line[cnt].r) swap(line[cnt].l,line[cnt].r);
        }
    }
    for(int i = 1; i <= M ; i ++){
        q[i].l = read(); q[i].r = read();
        q[i].id = i;
    }
    sort(q + 1,q + 1 + M,cmp);
    sort(line + 1,line + 1 + cnt,cmp2);
    int f = 1;
    for(int i = 1; i <= M ; i ++){
        while(f <= cnt && line[f].r <= q[i].r){
            add(line[f++].l,1);
        }
        ans[q[i].id] = getsum(q[i].l);
    }
    for(int i = 1; i <= M ; i ++){
        Pri(ans[i]);
    }
    return 0;
}
I

J.2:11:54 solved by gbs

队友写的

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <map>
#include <set>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

typedef long long LL;
const int maxn = 1e6 + 15;
const int mod = 1e9 + 7;
vector<int> pn[maxn + 15] ;
int th_inv[maxn + 15] ;
int high1[maxn+15];
int quick_mi(LL a, LL k)
{
    LL ans = 1;
    while (k)
    {
        if (k & 1)
        {
            ans *= a;
            ans %= mod;
        }
        a *= a;
        a %= mod;
        k >>= 1;
    }
    return ans;
}
int the_hight;
int find_hight(int nowi,int fu)
{
    int nowa = pn[nowi].size();
    if (fu != 0)
    {
        nowa--;
    }
    if (nowa == 0)
    {
        return high1[nowi] = 1;
    }
    for (unsigned int i=0; i<pn[nowi].size(); i++)
    {
        if (pn[nowi][i] == fu)
        {
            continue;
        }
        high1[nowi] = max(high1[nowi],find_hight(pn[nowi][i],nowi)+1);
    }
    return high1[nowi];
}
int inva(int a)
{
    if (th_inv[a] == 0)
        return th_inv[a] = quick_mi(a,mod-2);
    return th_inv[a];
}


int the_ans(int nowi, int fu,int di)
{
    int now_ans = 0;
    if (di + high1[nowi] != the_hight)
    {
        return 1;
    }
    int nowa = pn[nowi].size();
    if (fu != 0)
    {
        nowa--;
    }
    if (nowa == 0)
    {
        return 0;
    }
    for (unsigned int i=0; i<pn[nowi].size(); i++)
    {
        if (pn[nowi][i] == fu)
        {
            continue;
        }
        now_ans  = (0LL + now_ans  + the_ans(pn[nowi][i],nowi,di+1))%mod;
    }
    //cout<<nowi <<' '<<nowa<<' '<<now_ans <<endl;
    now_ans  = (1LL * now_ans  *inva(nowa))%mod;
    now_ans  = quick_mi(now_ans ,nowa);
    //cout<<"*"<<' '<<nowi<<' '<<now_ans <<endl;
    return now_ans ;

}
int main()
{
    int n;
    int a, b;
    cin >> n;
    for (int i = 0; i < n-1; i++)
    {
        scanf("%d%d", &a, &b);
        pn[a].push_back(b);
        pn[b].push_back(a);
    }
    find_hight(1,0);
    the_hight = high1[1];
    //printf("%d
",(the_ans(1,0,0)+mod)%mod  );
    printf("%d
",(1-the_ans(1,0,0)+mod)%mod  );

#ifdef VSCode
    system("pause");
#endif
    return 0;
}
J

K.00:49:48 solved by gbs

队友写的

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <map>
#include <set>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>


using namespace std;

typedef long long LL;

int xxnn[1005];
int yynn[1005];
struct pointa{
    int xi;
    int yi;
    pointa(int x1 =0,int y1 =0)
    {
        xi =x1;
        yi = y1;
    }
    bool operator <(const pointa & s1)const{
        if (xi!= s1.xi)
            return this->xi <s1.xi;
        return this->yi <s1.yi;
    }
    bool operator ==(const pointa & s1)const{
        return (this->xi ==s1.xi)&&(this->yi ==s1.yi);
    }

};

int main()
{
    int n;
    cin >>n;
    map<pointa,int>s1;
    for (int i=0; i<n; i++)
    {
        scanf("%d%d",&xxnn[i],&yynn[i]);
        if (s1[pointa(xxnn[i],yynn[i])] >=1)
        {
            n--;
            i--;
            continue;
        }
        else
        {
            s1[pointa(xxnn[i],yynn[i])]=1;
            xxnn[i] *= 2;
            yynn[i] *= 2;
        }
        
        
    }
    int fin_ans = 0;
    int llx;
    int lly;
    map<pointa,int>map1;
    for (int i=0; i<n; i++)
    {
        for (int j=i; j<n; j++)
        {
            llx = (xxnn[i]+xxnn[j])/2;
            lly = (yynn[i]+yynn[j])/2;
            if (xxnn[i]==xxnn[j] && yynn[i]==yynn[j])
            {
                map1[pointa(llx,lly)]+=1;
            }
            else
            {
                map1[pointa(llx,lly)]+=2;
            }
            
            fin_ans = max(fin_ans,map1[pointa(llx,lly)]);
        }
    }
    printf("%d
",n-fin_ans);




#ifdef VSCode
    system("pause");
#endif
    return 0;
}
K

L.3:36:27(-4) solved by zcz,hl

预处理出任意两点间，红点朝上翻滚到另一点红点朝上需要的步数

就是个旅行商问题了

状压dp入门门槛

#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++)  
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))  
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x)  
#define Pri(x) printf("%d
", x)
#define Prl(x) printf("%lld
",x)  
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long  
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second 
typedef vector<int> VI;
int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();}
while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
const double PI = acos(-1.0);
const double eps = 1e-9;
const int maxn = 1 << 16;
const LL INF = 1e18;
const int mod = 1e9 + 7; 
int N,M,K;
LL dis[4005][4005];

void init(){
    dis[0][0]=0;
    int k=3;
    int cnt=1;
    for(int i=1;i<=4000;i++)
    {
        if(cnt%4==0)
        {

            dis[i][0]=dis[0][i]=cnt;
        }
        else
        {
            dis[i][0]=k;
            dis[0][i]=k;
        }
        dis[i][1]=dis[1][i]=dis[i][0]+1;
        k++;
        cnt++;
    }
    for(int i=2;i<=4000;i++)
    {
        for(int j=2;j<=4000;j++)
        {
            dis[i][j]=i+j;
        }
    }
    dis[1][1]=6;
    dis[1][2]=dis[2][1]=5;
    dis[1][3]=dis[3][1]=6;
    dis[2][2]=4;
} 
PII node[20];
LL MAP[20][20];
LL dp[20][maxn];
int main(){
    init();
    int T = read();
    while(T--){
        Sca(N);
        for(int i = 0; i < N ; i ++){
            node[i].fi = read();
            node[i].se = read();
        }
        for(int i = 0; i < N ; i ++){
            for(int j = 0; j < N ; j ++){
                MAP[i][j] = dis[abs(node[i].fi - node[j].fi)][abs(node[i].se - node[j].se)];
            }
            MAP[N][i] = MAP[i][N] = dis[abs(node[i].fi)][abs(node[i].se)];
        }
        int ed = (1 << N);
        for(int i = 0 ; i <= N ; i ++){
            for(int j = 0 ; j < ed; j ++) dp[i][j] = INF;
        }
        dp[N][0] = 0;
        for(int i = 0 ; i < ed; i ++){
            for(int j = 0 ; j <= N ; j ++){
                if(dp[j][i] == INF) continue;
                for(int k = 0; k < N ; k ++){
                    if(i & (1 << k)) continue;
                    int v = i | (1 << k);
                    dp[k][v] = min(dp[k][v],dp[j][i] + MAP[j][k]);
                }
            }
        }
        LL ans = INF;
        for(int i = 0 ; i < N ; i ++) ans = min(ans,dp[i][ed - 1]);
        Prl(ans);
    }
    return 0;
}
L

M.01:47:31(-4) solved by hl

因为眼睛不好使子序列看成了子串，敲完EXKMP还WA了一发

发现a串只要比b串中的某个位置大，a串后面就都符合，前提是当前位置前面需要找的出子序列和b串位置的前缀一样

树状数组维护前缀最大值，表示a串比这个字符大的时候，前缀最多能匹配多少个数，答案就是max(N - i + 1 + max(0 ~ a[i]))

#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++)  
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))  
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x)  
#define Pri(x) printf("%d
", x)
#define Prl(x) printf("%lld
",x)  
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long  
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second 
typedef vector<int> VI;
int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();}
while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
const double PI = acos(-1.0);
const double eps = 1e-9;
const int maxn = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7; 
int N,M,K;
char a[maxn],b[maxn];
int tree[maxn];
void add(int u,int v){
    for(;u <= 27 ; u += u & -u)tree[u] = max(tree[u],v);
}
int getmax(int u){
    int ans = -1;
    for(;u > 0; u -= u & -u)ans = max(ans,tree[u]);
    return ans;
}
int main(){
    Sca2(N,M);
    scanf("%s%s",a,b);
    int cnt = 0,ans = -1;
    b[M] = 'a' - 1;
    for(int i = 0 ; i <= 27; i ++) tree[i] = -1;    
    add(b[0] - 'a' + 2,0);
    for(int i = 0 ; i < N; i ++){
        int v = a[i] - 'a' + 2;
        int t = getmax(v - 1);
        if(~t) ans = max(ans,N - i + t);
        if(cnt < M&& a[i] == b[cnt]){
            cnt++;
            add(b[cnt] - 'a' + 2,cnt);
        }
    }
    Pri(ans);
    return 0;
}
M

相关推荐