2019年第二阶段我要变强个人训练赛第十七场

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const ll mod=1e9+7;
 5 const int N=2e6+10;
 6 ll c[N],b[N];
 7 ll n,k,a,ans;
 8 ll quick(ll a,ll b){
 9     ll res=1;
10     while (b){
11         if (b&1){
12             res=res*a%mod;
13         }
14         a=a*a%mod;
15         b=b>>1;
16     }
17     return res;
18 }
19  
20 ll inv(ll x){
21     return quick(x,mod-2);
22 }
23  
24 int main()
25 {
26     c[0]=1;
27     scanf("%lld%lld",&n,&k);
28     for (int i=1;i<=n;i++)
29     {
30         scanf("%lld",&a);
31         b[a]++;
32         c[i]=c[i-1]*i%mod;
33     }
34     ans=c[n];
35     for (int i=0;i<=k;i++){
36         if (b[i]){
37             ans=ans*inv(c[b[i]])%mod;
38         }
39     }
40     cout<<ans<<endl;
41  
42 }

View Code

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3  
 4 long long n,a;
 5 long long ans;
 6 int main()
 7 {
 8     scanf("%lld",&n);
 9     for (int i=1;i<=n;i++)
10     {
11  
12         scanf("%lld",&a);
13         ans=ans|a;
14     }
15     cout<<ans<<endl;
16 }

View Code

 1 #include<bits/stdc++.h>
 2  
 3 using namespace std;
 4 typedef long long ll;
 5 const int N=1e6+10;
 6 struct node
 7 {
 8     ll to,next,w;
 9 } e[N*2];
10 ll t,n,k,h[N],d[N],ans;
11 map<ll,ll>mp;
12  
13 void add(ll u,ll v,ll w)
14 {
15     t++;
16     e[t].to=v;
17     e[t].next=h[u];
18     h[u]=t;
19     e[t].w=w;
20 }
21  
22 void dfs(ll x,ll fa,ll y)
23 {
24     mp[y]++;
25     d[x]=y;
26     for (int i=h[x]; i; i=e[i].next)
27     {
28         ll v=e[i].to;
29         if (v==fa) continue;
30         dfs(v,x,y^e[i].w);
31     }
32 }
33  
34 int main()
35 {
36     scanf("%lld%lld",&n,&k);
37     for (int i=1; i<n; i++)
38     {
39         ll u,v,w;
40         scanf("%lld%lld%lld",&u,&v,&w);
41         add(u,v,w);
42         add(v,u,w);
43     }
44     dfs(1,1,0);
45  
46     for (int i=1; i<=n; i++)
47     {
48         if ((d[i]^k)==d[i])
49         {
50             ans+=mp[d[i]^k]-1;
51         }
52         else
53         {
54             ans+=mp[d[i]^k];
55         }
56     }
57     printf("%lld
",ans/2);
58 }

View Code

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const ll mod=1e9+7;
 5 const int N=2e6+10;
 6 char c[N];
 7 ll n,sum1[N],sum2[N],k,a,ans=0x3f3f3f3f,pos;
 8  
 9 int main()
10 {
11     scanf("%d",&n);
12     scanf("%s",c+1);
13     for (int i=1;i<=n;i++){
14         sum1[i]=sum1[i-1]+(c[i]=='.');
15     }
16     for (int i=n;i>=1;i--){
17         sum2[i]=sum2[i+1]+(c[i]=='#');
18     }
19     for (int i=0;i<=n;i++){
20         ans=min(ans,i-sum1[i]+(n-i)-sum2[i+1]);
21     }
22     printf("%d
",ans);
23 }

View Code

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const ll mod=1e9+7;
 5 const int N=2e6+10;
 6 const ll inf=0x3f3f3f3f3f3f3f3f;
 7 ll a[N],ans=inf;
 8 ll n,d,an,sum,f,aa;
 9 int main()
10 {
11     scanf("%lld",&n);
12     for (int i=1; i<=n; i++)
13     {
14         scanf("%lld",&a[i]);
15     }
16     for (int i=-1; i<=1; i++)
17     {
18         for (int j=-1; j<=1; j++)
19         {
20             a[1]=a[1]+i;
21             a[2]=a[2]+j;
22             sum=0;
23             f=0;
24             d=a[2]-a[1];
25             aa=a[2];
26             for (int k=3; k<=n; k++)
27             {
28                 an=aa+d;
29                 if (abs(an-a[k])>1)
30                 {
31                     f=1;
32                     break;
33                 }
34                 else sum+=abs(an-a[k]);
35                 aa=an;
36             }
37             a[1]=a[1]-i;
38             a[2]=a[2]-j;
39             if (f) continue;
40             ans=min(ans,sum+abs(i)+abs(j));
41         }
42     }
43     if (ans==inf) printf("-1
");
44     else printf("%lld
",ans);
45 }

View Code

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 typedef long long ll;
 5 
 6 ll quick(ll a,ll b) {
 7     ll res = 1;
 8     while (b) {
 9         if (b & 1) {
10             res = res * a;
11         }
12         a = a * a;
13         b = b >> 1;
14     }
15     return res;
16 }
17 
18 ll check(ll x) {
19     return quick(2, x + 1) - x - 2;
20 }
21 ll n,k,l,r;
22 int main() {
23     int t;
24     scanf("%d", &t);
25     while (t--) {
26         scanf("%lld%lld", &n, &k);
27         if (n == 2 && k == 3) {
28             printf("No
");
29             continue;
30         }
31         int p = 1;
32         for (int i = 1;; i++) {
33             if ((quick(4, i) - 1) / 3 > k) {
34                 if ((quick(4, i - 1) - 1) / 3 == k) {
35                     p = i - 1;
36                 } else {
37                     p = i;
38                 }
39                 break;
40             }
41         }
42         if (p > n) {
43             printf("No
");
44             continue;
45         }
46         printf("Yes ");
47         l = 1;
48         r = 63;
49         while (l < r) {
50             int mid = (l + r) >> 1;
51             if (check(mid) >= k) {
52                 r = mid;
53             } else {
54                 l = mid + 1;
55             }
56         }
57         if (check(l) <= k) {
58             printf("%lld
", max(0ll, n - l));
59         } else {
60             printf("%lld
", max(0ll, n - l + 1));
61         }
62     }
63 }

View Code

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N=310;
const ll p=998244353;
ll n,a[N],f[N*N],g[N*N],sum,all,mid;

int main()
{
    while (~scanf("%lld",&n))
    {
        sum=0;
        all=1;
        for (int i=1; i<=n; i++)
        {
            scanf("%d",&a[i]);
            sum+=a[i];
            all=all*3%p;
        }
        mid=sum/2;
        memset(f,0,sizeof(f));
        f[0]=1;
        ll res=0;
        for (int i=1; i<=n; i++)
        {
            for (int j=sum-a[i]; j>=0; j--)
            {
                f[j+a[i]]=(f[j+a[i]]+f[j]*2%p)%p;
            }
        }

        for (int i=0; i<=mid; i++)
        {
            res=(res+f[i])%p;
        }
        if (sum%2==0)
        {
            memset(g,0,sizeof(g));
            g[0]=1;
            for (int i=1; i<=n; i++)
            {
                for (int j=sum-a[i]; j>=0; j--)
                {
                    g[j+a[i]]=(g[j+a[i]]+g[j])%p;
                }

            }
            res=(res-g[mid]+p)%p;
        }
        printf("%lld
",(all-res*3%p+p)%p);
    }
}

#include<bits/stdc++.h>

using namespace std;
vector<pair<string,int> >vec;
int n,m,k,len;
char str[1000002];
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=0; i<n; i++)
    {
        scanf("%s",str);
        vec.push_back(make_pair(str,i));
    }
    sort(vec.begin(),vec.end());
    for (int i=1; i<=m; i++)
    {
        scanf("%d",&k);
        scanf("%s",str);
        string s=str;
        len=s.size();
        int kk=lower_bound(vec.begin(),vec.end(),make_pair(s,0))-vec.begin();
        if (kk+k-1<n&&vec[kk+k-1].first.size()>=len&&vec[kk+k-1].first.substr(0,len)==s)
        {
            printf("%d
",vec[kk+k-1].second+1);
        }
        else
        {
            printf("-1
");
        }
    }
}