1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include <bits/stdc++.h>
#define mk(x,y) make_pair(x,y)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define max(x,y) ((x)<(y)?(y):(x))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;
typedef long long ll;
#define int long long
const int N=1e6+7,mod=998244353,inf=1e9+7;

void solve()
{
    string s;
    cin>>s;
    map<char,int>vis;
    int cnt=0;
    for(auto x:s){
        if(vis[x]==0)cnt++;
        vis[x]++;
    }
    if(vis['i'])cnt--;
    cout<<cnt<<endl;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T=1;
    // cin>>T;
    while(T--) {
        solve();
    }
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

#include <bits/stdc++.h>
#define mk(x,y) make_pair(x,y)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define max(x,y) ((x)<(y)?(y):(x))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;
typedef long long ll;
#define int long long
const int N=1e6+7,mod=998244353,inf=1e9+7;
int a[N][6];
void sol(string s,int k)
{
    int tot=1,now=0;
    for(int i=0;i<s.length();++i) {
        if(s[i]=='.'||s[i]=='/') {
            ++tot;
            now=0;
            continue;
        }
        now=now*10+s[i]-'0';
        a[k][tot]=now;
    }

}
void solve()
{
    string s;
    cin>>s;
    sol(s,0);
    int n;
    cin>>n;
    for(int i=1;i<=n;++i) {
        cin>>s;
        sol(s,i);
        int ans=1;
        for(int j=1,tmp=a[0][5];j<=4&&tmp>0;++j) {
            int x=min(tmp,8);
            if((a[0][j]>>(8-x))!=(a[i][j]>>(8-x))) {
                ans=0;
                break;
            }
            tmp-=x;
        }
        if(ans)  printf("YES\n");
        else  printf("NO\n");
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T=1;
    // cin>>T;
    while(T--) {
        solve();
    }
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

#include <bits/stdc++.h>
#define mk(x,y) make_pair(x,y)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define max(x,y) ((x)<(y)?(y):(x))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;
typedef long long ll;
#define int long long
const int N=1e6+7,inf=998244353,mod=1e9+7;
ll a[11],pre[39];
ll qpow(ll x,ll k)
{
    ll ans=1;
    while(k) {
        if(k&1)  ans=ans*x%mod;
        x=x*x%mod;
        k>>=1;
    }
    return ans;
}
void solve()
{
    bool flag=0;
    ll ans=0;
    int n;
    cin>>n;
    for(int i=0;i<=9;++i) {
        cin>>a[i];
        if(i!=0&&flag==0&&a[i]>0) {
            flag=1;
            ans=qpow(10,n-1)*i%mod;
            --n;
            --a[i];
        }
    }
    if(flag==0||(n==0&&a[0])) {
        printf("0\n");
        return;
    }
    for(int i=0;i<=9;++i) {
        if(n==0)  break;
        if(!a[i])  continue;
        ll res=min(a[i],n),cnt=0,sum=0;
        for(ll j=0;res>0;res>>=1,++j) {
            if(res&1)  sum=(sum+pre[j]*qpow(10,cnt)%mod)%mod,cnt+=1ll<<j;
        }
        sum=sum*i%mod;
        ans=(ans+sum*qpow(10,n-cnt)%mod)%mod;
        n-=cnt;
    }
    printf("%lld\n",ans);
    
}
signed main()
{
    pre[0]=1;
    for(int i=1;i<=32;++i) {
        pre[i]=(pre[i-1]+pre[i-1]*qpow(10,1ll<<(i-1))%mod)%mod;
    }
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T=1;
    cin>>T;
    while(T--) {
        solve();
    }
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

#include <bits/stdc++.h>
#define mk(x,y) make_pair(x,y)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define max(x,y) ((x)<(y)?(y):(x))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;
typedef long long ll;
const int N=1e6+7,mod=998244353,inf=1e9+7;

struct Node{
    int l,r,id;
};

bool cmp(Node a,Node b){
    if(a.l==b.l)return a.r<b.r;
    return a.l<b.l;
}
priority_queue<pii> pq;
vector<int> ans;
void solve()
{
    int n;
    cin>>n;
    vector<Node>a;
    for(int i=1;i<=n;i++){
        int l,r;
        cin>>l>>r;
        a.push_back(Node{l,r,i});
    }
    sort(a.begin(),a.end(),cmp);
    int now=0;
    for(int i=0;i<n;i++){
        if(now>=a[i].l) {
            pq.push(mk(-a[i].r,a[i].id));
            continue;
        }
        while(!pq.empty()&&-pq.top().first<now)  pq.pop();
        while(now<a[i].l&&!pq.empty()) {
            ++now;
            ans.push_back(pq.top().second);
            pq.pop();
            while(!pq.empty()&&-pq.top().first<now)  pq.pop();
        }
        if(now<a[i].l)  break;
        pq.push(mk(-a[i].r,a[i].id));
    }
    while(!pq.empty()&&-pq.top().first<now)  pq.pop();
    while(!pq.empty()) {
        ++now;
        ans.push_back(pq.top().second);
        pq.pop();
        while(!pq.empty()&&-pq.top().first<now)  pq.pop();
    }
    printf("%d\n",now);
    for(auto x:ans)  printf("%d ",x);
    printf("\n");
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T=1;
    // cin>>T;
    while(T--) {
        solve();
    }
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

#include <bits/stdc++.h>
#define mk(x,y) make_pair(x,y)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define max(x,y) ((x)<(y)?(y):(x))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;
typedef long long ll;
const int N=1e6+7,mod=998244353,inf=1e9+7;
int cnt[4],a[N<<1],sum[N<<1][4],n;
bool check(int l,int r)
{
    for(int j=0;j<=2;++j)
        if(sum[l][j]-sum[r][j]>cnt[j])  return 0;
    return 1;
}
void solve()
{
    string s;
    cin>>cnt[0]>>cnt[1]>>cnt[2]>>s;
    n=s.length();
    for(int i=1;i<=n;++i) {
        a[i]=a[i+n]=s[i-1]-'0';
    }
    n<<=1;
    int ans=0;
    for(int i=n-1;i>=1;--i) {
        int k=a[i]+a[i+1];
        for(int j=0;j<=2;++j)  sum[i][j]=sum[i+2][j];
        ++sum[i][k];
        int l=1,r=(n-i+1)/2,tmp=0;
        while(l<=r) {
            int mid=(l+r)>>1;
            if(check(i,i+mid*2))  tmp=mid,l=mid+1;
            else  r=mid-1;
        }
        tmp=min(tmp,n/4);
        ans=max(ans,tmp*2);
    }
    printf("%d\n",ans);

}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T=1;
    // cin>>T;
    while(T--) {
        solve();
    }
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

#include <bits/stdc++.h>
#define mk(x,y) make_pair(x,y)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define max(x,y) ((x)<(y)?(y):(x))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;
typedef long long ll;
typedef double db;
const int N=1e3+7,mod=998244353;
const ll inf=1e16+7;
struct node {
    db x,y;
}b[5],a[N];
int tmp1,tmp2,n,num1,num2,m,q[5];
db f[N][N],dis[N][5];
bool vis[5];
db DIS(node u,node v) {
    return sqrt((u.x-v.x)*(u.x-v.x)+(u.y-v.y)*(u.y-v.y));
}
void dfs(int now)
{
    if(now==4) {
        for(int i=1;i<=n;++i) {
            node last=a[i];
            db sum=0;
            for(int j=1;j<=3;++j) {
                sum+=DIS(last,b[q[j]]);
                dis[i][j]=min(dis[i][j],sum+DIS(b[q[j]],b[4]));
                last=b[q[j]];
            }
        }
        return ;
    }
    for(int i=1;i<=3;++i) {
        if(vis[i])  continue;
        vis[i]=1;
        q[now]=i;
        dfs(now+1);
        vis[i]=0;
    }
}
void solve()
{
    cin>>tmp1>>tmp2>>n>>num1>>num2;
    m=max(ceil(1.0*tmp1/num1),ceil(1.0*tmp2/num2));
    for(int i=1;i<=4;++i) {
        cin>>b[i].x>>b[i].y;
    }
    for(int i=1;i<=n;++i) {
        cin>>a[i].x>>a[i].y;
        for(int j=1;j<=3;++j)  dis[i][j]=inf;
    }
    dfs(1);
    for(int j=1;j<=m;++j)  f[0][j]=inf;
    for(int i=1;i<=n;++i) {
        for(int j=1;j<=m;++j) {
            f[i][j]=inf;
            for(int k=0;k<=3&&k<=j;++k)  
                f[i][j]=min(f[i][j],f[i-1][j-k]+dis[i][k]);
        }
    }
    printf("%.10lf",f[n][m]);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T=1;
    // cin>>T;
    while(T--) {
        solve();
    }
    return 0;
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

#include <bits/stdc++.h>
#define mk(x,y) make_pair(x,y)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define max(x,y) ((x)<(y)?(y):(x))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;
typedef long long ll;
typedef double db;
#define int long long
const int N=1e6+7,mod=998244353;
const int inf=1e14+7;
int f[N][21][3],dep[N];
pii g[N][2];
vector<int> nx[N];
bool bk[N];
int n,m;
void dfs(int x,int fa,int last)
{
    dep[x]=dep[fa]+1;
    if(bk[x])  last=0,g[x][0]=mk(0,x);
    else  ++last;
    f[x][0][0]=fa;
    for(auto y:nx[x]) {
        if(y==fa)  continue;
        dfs(y,x,last);
        if(g[y][0].first+1<g[x][0].first)  g[x][0]=mk(g[y][0].first+1,y);
    }
    for(auto y:nx[x]) {
        if(y==fa||y==g[x][0].second)  continue;
        if(g[y][0].first+1<g[x][1].first)  g[x][1]=mk(g[y][0].first+1,y);
    }
    

}
void dfs2(int x,int fa,int last)
{
    if(x!=1) {
        int k=0;
        if(g[fa][0].second==x)  k=1;
        if(g[fa][k].first+1<g[x][0].first) {
            g[x][1]=g[x][0];
            g[x][0]=mk(g[fa][k].first+1,fa);
        } else if(g[fa][k].first+1<g[x][1].first) {
            g[x][1]=mk(g[fa][k].first+1,fa);
        }
    }
    for(auto y:nx[x]) {
        if(y==fa)  continue;
        dfs2(y,x,last);
    }
    f[x][0][1]=min(f[x][0][1],g[x][0].first*3+n-dep[x]);
    f[x][0][2]=min(f[x][0][2],g[x][0].first*3+dep[x]);
}
int LCA(int x,int y)
{
    if(dep[x]<dep[y])  swap(x,y);
    for(int i=20;i>=0;--i)
        if(dep[f[x][i][0]]>=dep[y]) {
            x=f[x][i][0];
        }
    if(x==y) {
        return x;
    }
    for(int i=20;i>=0;--i)
        if(f[x][i][0]!=f[y][i][0]) {
            x=f[x][i][0];y=f[y][i][0];
        }
    return f[x][0][0];
}
void solve()
{
    
    cin>>n>>m;
    for(int i=1;i<n;++i) {
        int x,y;
        cin>>x>>y;
        nx[x].push_back(y);
        nx[y].push_back(x);
    }
    for(int i=0;i<=n;++i) {
        g[i][0]=g[i][1]=mk(inf,0);
        for(int j=0;j<=20;++j)  f[i][j][1]=inf,f[i][j][2]=inf;
    }
    for(int i=1;i<=m;++i) {
        int x;
        cin>>x;
        bk[x]=1;
    }
    dfs(1,0,inf);
    dfs2(1,0,inf);
    for(int j=1;j<=20;++j)
        for(int i=1;i<=n;++i) {
            f[i][j][0]=f[f[i][j-1][0]][j-1][0];
            f[i][j][1]=min(f[i][j-1][1],f[f[i][j-1][0]][j-1][1]);
            f[i][j][2]=min(f[i][j-1][2],f[f[i][j-1][0]][j-1][2]);
        }
    int q;
    cin>>q;
    while(q--) {
        int x,y;
        cin>>x>>y;
        int lca=LCA(x,y);
        int ans=dep[x]+dep[y]-dep[lca]*2,mi=f[lca][0][1]-n+dep[x],tmpx=x,tmpy=y;
        for(int i=20;i>=0;--i)
            if(dep[f[tmpx][i][0]]>=dep[lca]) {
                mi=min(mi,f[tmpx][i][1]-n+dep[x]);
                tmpx=f[tmpx][i][0];
            }
        for(int i=20;i>=0;--i)
            if(dep[f[tmpy][i][0]]>=dep[lca]) {
                mi=min(mi,f[tmpy][i][2]-dep[lca]+dep[x]-dep[lca]);
                tmpy=f[tmpy][i][0];
            }
        ans+=mi;
        ans=min(ans,(dep[x]+dep[y]-dep[lca]*2)*2);
        printf("%lld\n",ans);
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T=1;
    // cin>>T;
    while(T--) {
        solve();
    }
    return 0;
}