周末练习1

传送门：点击打开链接

B - B

You are given an array a consisting of n elements a₁, a₂, ..., a_n. Array a has a special property, which is:

You are given the array a with some lost elements from it, each lost element is replaced by -1. Your task is to find all the lost elements again, can you?

4
5 10
1 2 3 4 5
4 10
7 -1 9 -1
6 7
5 -1 -1 1 2 3
6 10
5 -1 7 -1 9 0

1 2 3 4 5
7 8 9 0
5 6 0 1 2 3
5 6 7 8 9 0

#include <bits/stdc++.h>
using  namespace std;
int n,m;
int a[100005];
int pos;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        for(int i=1;i<=n;i++)
        {
            if(a[i]!=-1)
            {
                pos=i;
                break;
            }
        }
        for(int i=pos+1;i<=n;i++)
        {
            a[i] = (a[i-1] + 1) % m;
        }
        for(int i=pos-1;i>=1;i--)
        {
            a[i] =(a[i+1] - 1 + m ) % m;
        }
        for(int i=1;i<=n;i++)
        {
            printf("%d ",a[i]);
        }
        printf("\n");
    }
    return 0;
}

1
8 5
abcabdca
1 8 c
1 15 b
4 9 a
5 25 d
2 7 c

2
4
3
3
2

#include <iostream>
#include <map>
#include <cstring>
#include <cstdio>
using  namespace std;
typedef long long LL;
int n,q;
char s[10005];
 
int num[26][10005];  //i个字母在j位置前出现次数
 
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d",&n,&q);
        scanf("%s",&s);
        for (int i=0;i<26 ; i++)
        {
            int nnn=0;
            for(int j=0;j<n;j++)
            {
                if(s[j]-'a' == i)
                {
                    nnn++;
                }
                num[i][j+1] = nnn;  //此处j+1是为了使字符从1开始，否则比较容易乱
            }
            //cout<<nnn<<"---"<<endl;
        }
 
        while(q--)
        {
            LL l, r ;
 
            char ch;
            scanf("%lld %lld %c",&l,&r,&ch);
            LL sum_l = 0;
            LL sum_r = 0;
            l--;
            sum_l = (l / n) * num[ch-'a'][n] + num[ch-'a'][l % n];  //1-l-1的某个字符的个数
            sum_r = (r / n) * num[ch-'a'][n] + num[ch-'a'][r % n]; //1-r的某个字符的个数
           /* cout<<"l/n="<<l/n<<endl; 
            cout<<"r/n="<<r/n<<endl;
            cout<<"l%n="<<(l+n)%n<<endl;
            cout<<"r%n="<<(r+n)%n<<endl;
            cout<<"sum_l="<<sum_l<<endl;
            cout<<"sum_r="<<sum_r<<endl;*/
            LL sum = sum_r - sum_l;  //相减即为结果
            printf("%lld\n",sum);
        }
    }
    return 0;
}

2
8
2 1 3 4 6 5 7 9
6
4 2 7 9 8 10

3
1

#include <bits/stdc++.h>
#define INF 0x7f7f7f7f
#define ll long long
#define mod 1000000007
using namespace std;
int dpf[1000010],dpb[1000010];
int a[1000010];
int main()
{
    int t;
    scanf("%d",&t);//cin>>t;
    while(t--)
    {
        int n,i,res=0;
        scanf("%d",&n);//cin>>n;
        scanf("%d",&a[0]);//cin>>a[0];
        dpf[0]=a[0];
        for(i=1;i<n;i++)
        {
            scanf("%d",&a[i]);//cin>>a[i];
            dpf[i]=max(a[i],dpf[i-1]);  //正像最大
        }
        dpb[n-1]=a[n-1];
        for(i=n-2;i>=0;i--)
        {
            dpb[i]=min(a[i],dpb[i+1]); //反向最小
        }
        for(i=1;i<n-1;i++)
        {
            if(a[i]>=dpf[i-1]&&a[i]<=dpb[i+1])   //关键
            {
                res++;
            }
        }
        printf("%d\n",res);//cout<<res<<endl;
    }
   return 0;
}

3
3 3
111
101
111
4 4
1111
0111
1000
1111
4 5
10101
01010
10101
01010

0
2
-1

#include <bits/stdc++.h>
using  namespace std;
int n,m;
char s[100];
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
 
        cin>>n>>m;
        int num_z = 0;
        int num_o = 0;
        bool flag = true;
        for(int i = 1; i <= n; i++)
        {
            cin>>s;
            for(int j=0;j<m;j++)
            {
                if(i==1 || j==0 || i==n || j==m-1)
                {
                    if(s[j]=='0')
                    {
                        flag = false;
                        num_o ++;
                    }
                }
                if(s[j] == '1')
                    num_z++;
            }
        }
        if(flag==true)
        {
            printf("0\n");
            continue;
        }
        int num = 2*n + 2*m - 4;
        if(num > num_z)
        {
            printf("-1\n");
            continue;
        }
        printf("%d\n",num_o);
    }
    return 0;
}

Since the problem set was hard, here is an easy task for you to solve.

You are given an array a consisting of n integers, and your task is to calculate the summation of the multiplication of all subsets of array a. (See the note for more clarifications)

A subset of an array a is defined as a set of elements that can be obtained by deleting zero or more elements from the original array a.

3
3
1 2 3
2
3 5
1
4512

23
23
4512

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
const int M = 100005;
typedef long long LL;
int a[M];
LL sum[M];
int main()
{
    int T;
    int n;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i = 1 ; i <= n ; i++)
        {
            scanf("%d",&a[i]);
        }
        sum[1] = a[1] ;
        for(int i = 2 ; i <= n; i++)
        {
            sum[i] = (sum[i-1] + a[i] + sum[i-1] * a[i]) % mod;
        }
        printf("%lld\n",sum[n]%mod);
    }
    return 0;
}