第八周学习总结

追随远方的某R · CSDN · · 2020-01-01 00:00

本周学的东西比较少，因为军训嘛，CF也没怎么打，这周最主要学的应该还是一个关于map的东西，一些做题刷到的东西。

首先关于map

map是Stl的一个容器，他有两个性质：
1.可以提供任意类型下表（key）对应任意类型值（value）的关联。

关于第一个性质
类比数组，数组是一个整数下标对应一个任意类型的值，而map就是一个任意类型的下标对应了一个任意类型的值。

2.key是唯一的不可重复（这是为map的不可重复性）

关于第二个性质
这个要记住，你已经插入的key不可以通过insert的方式来覆盖更新这个key对应的值。

和这个有直接关系的是一道在训练赛中做的题

https://codeforces.com/problemset/problem/755/B

题意就是俩人，每个人知道不同的字符串（单词），A先说，B后说，A说过的单词B就不能再说了

思路：我的思路比较朴素，直接开了两个字符串数组，然后输入，统计一下两人知道的相同的单词个数然后就可以

后面判断胜负有很多种方法这里说两个最巧妙的。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    //freopen("in.txt","r",stdin);
    int n,m,c1=0;
    cin>>n>>m;
    string s1[1010],s2[1010];
    for(int i=0;i<n;i++)
    {
        cin>>s1[i];
    }
    for(int i=0;i<m;i++)
    {
        cin>>s2[i];
        for(int j=0;j<n;j++)
        {
            if(s2[i]==s1[j])
            {
                c1++;
            }	
        }
    }
    if(c1%2!=0)
    {
      n+=c1/2+1;
      m+=c1/2;
    }
    if(n>m)
    {
        cout<<"YES"<<endl;
    }
    else
    {
        cout<<"NO"<<endl;
    }
    return 0;
}

这种判断方法就是找一下“共有单词”可以视为给A和B放多发了一些牌

#include <bits/stdc++.h>
using namespace std;
int main()
{
    //freopen("in.txt","r",stdin);
    int n,m;
    cin>>n>>m;
    string s1[1010],s2[1010];
    for(int i=0;i<n;i++)
    {
        cin>>s1[i];
    }
    for(int i=0;i<m;i++)
    {
        cin>>s2[i];
    }
    int min1=min(n,m);
    int c1=0;
   for(int i=0;i<m;i++)
    {
        cin>>s2[i];
        for(int j=0;j<n;j++)
        {
            if(s2[i]==s1[j])
            {
                c1++;
            }
        }
    }
    if(c1%2)
    {
        n-=c1;
        m-=c1;
        if(n>=m)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
    else
    {
        n-=c1;
        m-=c1;
       if(n>m)
            cout<<"Yes"<<endl;
        else
            cout<<"NO"<<endl;
    }
    return 0;
}

这种方法涉及到一个先后手转换的思想，“公共区间”的作用就变成了先后手的转换。

这个题为啥wa了呢，，，我的统计出错了，思想还是很简单的，就是统计有些问题，我的统计居然写成了一重循环，，yue了

既然之前说了map，那么这题就用map来试一下
首先呢我么先来建立一个map

map<int,string>s1;
map<int,string>s2;

然后我们给map存一下数据

string s;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        cin>>s;
        s1[i]=s;
    }
    for(int i=0;i<m;i++)
    {
        cin>>s;
        s2[i]=s;
    }

然后我们统计一下“共有单词”

for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(s1[i]==s2[j])
                c1++;
        }
    }

然后进行一下计算

 if(c1%2)
    {
        n-=c1;
        m-=c1;
        if(n>=m)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
    else
    {
        n-=c1;
        m-=c1;
       if(n>m)
            cout<<"Yes"<<endl;
        else
            cout<<"NO"<<endl;
    }

ok了

二 TLE
总的来说这个东西共有五点原因
1.算法本身是有问题的，造成超时，比如使用了多重循环语句，这种情况能改语句就改语句，，是在不行就要换一种实现方法。
2.memset，这个东西并不像想象中的那么好，，会超时
这里要解释一下。
并非memset本身的debug和release效率比for循环要差。
而是当你在memset的时候如果对你开的整个数组进行的操作，那么就有可能造成超时，
比如，开始了个1e6的数组，95%的数据都只用了1e3以内，memset每次都对1e6的进行初始化，这样就浪费很多的时间。最终会超时。
3.cin与cout造成超时
之前也说过cin和cout对比c语言的scanf和printf会显得很慢，
至于你说的

ios::sync_with_stdio(0);
cout.tie(0);
cin.tie(0);

这些还是没法让cin和cout赶上scanf和printf的效率,所以就，，在遇到大量输入输出的时候就放弃cin和cout吧
4.
数组开的不够大，
数组开的不够大会造成很多情况，比如会造成非法访问，WA，当然也会造成TLE，这时候就要把数组开大一点。
5.
是第一个问题的一个拓展，比如判断一个数n是否是素数的这个问题上。
我们都知道应该从1到n进行遍历，可是这样虽然可行能得到正确答案却在时间复杂度上会有很大的影响。
进一步观察会发现，只需要遍历到sqrt（n）+1就可以判断了所以应该修改之前的遍历范围。

原文地址：访问原文地址
快照地址：访问文章快照

分享到微博