week2

第二周

Colorful Candies（at）

链接：

https://atcoder.jp/contests/abc210/tasks/abc210_c

思路：

滑动窗口，进一个出一个，统计map的最大值

俺是一坨垃圾代码QWQ:

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
int main()
{
    int n, k;
    cin >> n >> k;
    vector<int> num(n + 1, 0);
    map <int,int> s;
    int res = 0;
    for (int i = 0; i < n;i++)
        cin >> num[i];
    for (int j = 0; j < k;j++)
        {
            s[num[j]]++;
        }
    res = s.size();
    for (int i = k; i < n;i++)
    {
        if(s[num[i-k]]!=0)
            s[num[i - k]]--;
        if(s[num[i - k]]==0)
            s.erase(num[i - k]);
        s[num[i]]++;
        res = max(res, (int)s.size());
    }
    cout << res;
}

括号序列（lg）

链接：

https://www.luogu.com.cn/problem/P1241

思路：

因为阅读理解不过关卡了好久（求你能不能好好看题）。先对右括号匹配最近的左括号，如果匹配不成功就放弃。匹配完毕后再将没有匹配的括号进行匹配

俺是一坨垃圾代码QWQ:

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
int main()
{
    string str;
    cin >> str;
    vector<bool> vis(str.size() *2+1, 0);
    for (int i = 0; i < str.size();i++)
    {
        if(str[i]==')')
        {
            for (int j = i - 1; j >= 0;j--)
            {
                if(str[j]=='('&&vis[j]==0)
                {
                    vis[j] = 1;
                    vis[i] = 1;
                    break;
                }
                if(str[j]=='['&&vis[j]==0)
                    break;
            }
        }
        if(str[i]==']')
        {
            for (int j = i - 1; j >= 0;j--)
            {
                if(str[j]=='['&&vis[j]==0)
                {
                    vis[j] = 1;
                    vis[i] = 1;
                    break;
                }
                if(str[j]=='('&&vis[j]==0)
                    break;
            }
            
        }
    }
    for (int i = 0; i < str.size();i++)
    {
        if(vis[i]==0)
        {
            if((str[i]=='('||str[i]==')'))
            cout << "()";
            else
            cout << "[]";
        }
        else
            cout << str[i];
    }
    return 0;
}

AquaMoon_and_Two_Arrays（cf）

链接：

https://codeforces.com/contest/1546/problem/A

思路：

找规律，a,b和不一样就是-1，相等的话少就加，多就减，记录操作就行了。

俺是一坨垃圾代码QWQ:

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
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n,a1=0,b1=0;
        cin >> n;
        vector<int> a(n + 1);
        vector<int> b(n + 1);
        for (int i = 0; i < n;i++)
            {
                cin >> a[i];
                a1 += a[i];
            }
        
        for (int i = 0; i < n;i++)
        {
            cin >> b[i];
            b1 += b[i];
        }
        if(a1!=b1)
            cout << "-1" << endl;
        else
        {
            if(n==1)
                cout << 0 << endl;
            else
            {
                int ans = 0;
                for (int i = 0; i < n; i++)
                {
                    if(a[i]<b[i])
                        ans += b[i] - a[i];
                }
                cout << ans << endl;
                for (int i = 0, j = 0; i < n; i++)
                {
                    if(a[i]>b[i])
                    {
                        while(j<n&&a[j]>=b[j])
                            j++;
                        a[i]--;
                        a[j]++;
                        cout << i+1 << " " << j+1 << endl;
                        i--;
                    }
                }
            }
        }
    }
}

AquaMoon and Stolen String（cf）

链接：

https://codeforces.com/contest/1546/problem/B

思路：

因为只有一组没进行过操作，所以总的减去操作的，剩下的就是没被操作的
还有一种思路是因为是成对操作的，所以首字母出现次数为奇数的就是剩下的。

俺是一坨垃圾代码QWQ:

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
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n, m;
        cin >> n >> m;
        string t;
        vector<int> ans(m + 1);
        vector<int> an(m + 1);
        for (int j = 0; j < n;j++)
        {
            for (int i = 0; i < m;i++)
            {
                char x;
                cin >> x;
                ans[i] += x;
            }
        }
        for (int j = 0; j < n - 1;j++)
        {
            for (int i = 0; i < m;i++)
            {
                char x;
                cin >> x;
                an[i] += x;
            }
        }
        for (int i = 0; i < m;i++)
            putchar(ans[i] - an[i]);
        cout << endl;
    }
    return 0;
}

Arithmetic Sequence（at）

链接：

https://atcoder.jp/contests/arc123/tasks/arc123_a

思路：

相邻两个的相减结果相同，也就是（a+c）/2=b，基于这个b值，比较是同时增加a c还是只增加b。a c为奇数时要将其中一个加上1，结果数也要加1

俺是一坨垃圾代码QWQ:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int main()
{
    long long a, b, c,t=0;
    cin >> a >> b >> c;
    if((a+c)%2)
        {
            c++;
            t = 1;
        }
    if((a+c)/2>b)
        cout << (a + c) / 2 - b+t;
    else
        cout << (b - (a + c) / 2) * 2+t;
    return 0;
}

Increasing Triples（at）

链接：

https://atcoder.jp/contests/arc123/tasks/arc123_b

思路：

三列数，分别排序，三个指针顺次比对，递增结果数加一

俺是一坨垃圾代码QWQ:

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
int main()
{
    int n,ans=0;
    cin >> n;
    vector<int> a(n );
    vector<int> b(n );
    vector<int> c(n );
    for (int i = 0; i < n;i++)
        cin >> a[i];
    for (int i = 0; i < n;i++)
        cin >> b[i];
    for (int i = 0; i < n;i++)
        cin >> c[i];
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    sort(c.begin(),c.end());
    for (int i = 0,j=0,k=0,flag=0; i < n;i++)
    {
        int t = a[i];
        while(j<n&&b[j]<=t)
            j++;
        while(k<n&&c[k]<=b[j])
            k++;
        if(i<n&&j<n&&k<n&&a[i]<b[j]&&b[j]<c[k])
            ans++;
        j++;
        k++;
        
    }
    cout << ans;
    return 0;
}

Digits Sum（cf）

链接：

https://codeforces.com/contest/1553/problem/A

思路：

结果可推是x/10，如果结尾数为9，仍需要加1

俺是一坨垃圾代码QWQ:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int x;
        cin >> x;
        if(x<9)
            cout << 0 << endl;
        else
        {
            if(x%10==9)
                cout << x / 10 + 1 << endl;
            else
                cout << x / 10 << endl;
        }
    }
}

Reverse String（cf）

链接：

https://codeforces.com/contest/1553/problem/B

思路：

鸡掰题，其实很简单，就是在每个回文子串里寻找是否有目标串。

俺是一坨垃圾代码QWQ:

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
bool check(string now,string t)//有问题的check，直接写出bug
{
    int look = 0,vis=0;
    bool flag = 0;
    for (i=0; i < now.size();i++)
    {
        if(now[i]==t[0])
            vis = i;
        
        if(now[i]==t[look])
        {
            look++;
        }
        else if(now[i]!=t[look]&&look!=0)
            {
                i=vis+1;
                look = 0;
            }
        if(look==t.size())
            return 1;
    }
    if(look==t.size())
            return 1;
    return 0;
}
void solve()
{
    string s, t, now, cpy;
    cin >> s >> t;
    for (int i = 1; i <= s.size();i++)
    {
        bool ans = 0;
        cpy = s.substr(0, i);//substr取出子串
        now = cpy;
        now.erase(now.size() - 1);
        reverse(cpy.begin(), cpy.end());
        now += cpy;
        ans = check(now, t);
        if(now.find(t)!=-1)//直接用find就可找出子串
        {
            cout << "YES" << endl;
            return;
        }
    }
    cout << "NO" << endl;
}
int main()
{
    int x2;
    cin >> x2;
    while(x2--)
    {
        solve();
    }
    return 0;
}

Reverse String（cf）

链接：

https://codeforces.com/contest/1553/problem/C

思路：

dfs跑出所有的情况，再判断

俺是一坨垃圾代码QWQ:

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
string foot;
int res=10;
bool vis[10];
bool VIS[10];
void dfs(int step,int now)
{
    for (int i = now; i < 10;i++)
    {
            if(vis[i]==0&&VIS[i]==0)
            {
                foot[i] = '1';
                vis[i] = 1;
                dfs(step + 1,i);
                vis[i] = 0;

                foot[i] = '0'; 
                vis[i] = 1;
                dfs(step + 1,i);
                vis[i] = 0;
            }
        step=i+2;
    }
    if(step>=11)
    {
        int p=0,q=0;
	    for(int i=0;i<10;i++){
		if(i&1)p+=foot[i]-'0';
		else q+=foot[i]-'0';
		if(p-q>(10-i-1)/2||q-p>(10-i)/2){
			res=min(res,i+1);
			break;
		}
	    }
        return;
    }
}
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        cin >> foot;
        for (int i= 0; i < 10;i++)
        {
            if(foot[i]!='?')
            {
                VIS[i] = 1;
            }
        }
            dfs(1, 0);
        cout << res << endl;
        memset(vis, 0, sizeof(vis));
        memset(VIS, 0, sizeof(VIS));
        res = 10;
    }
}
赏

来根小鱼干好吗o( =·ω·= )m

支付宝
微信

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

20级的菜鸡，一条咸鱼，圈子小，由于天赐の礼物——脸盲，不认识几个人，只要你主动一点点我们就有故事⁄(⁄ ⁄•⁄ω⁄•⁄ ⁄)⁄。