周报4

补题1:秀恩爱分的快

题意:

做法：先读入照片的数据存起来，知道A,B的性别之后再遍历照片，按照异性进行cnt.有一个细节就是0和-0是无法区分的如果不用字符串读入的话。所以要字符串来存数据，后面再做判断，剩下的就简单遍历一下照片，然后relateA和relateB分开计算即可。

bool cmp(pair<double,int> a,pair<double,int> b){
    if(a.first!=b.first) return a.first>b.first;
    return a.second<b.second;
}
void solve(){         //补7-12秀恩爱分的快
    int n,m,k;
    pair<double,int> relateA[1005];
    pair<double,int> relateB[1005];
    cin>>n>>m;
    for(int i=0;i<1000;i++){  //init
        relateA[i].first=0;
        relateA[i].second=i;
        relateB[i].first=0;
        relateB[i].second=i;
    }
    string x;
    vector<string> vct[m];
    for(int i=0;i<m;i++){
        cin>>k;
        while(k--){
            cin>>x;
            vct[i].emplace_back(x);
        }
    }
    bool sexA=false,sexB=false;
    string A,B;
    int numa,numb;
    cin>>A>>B;
    if(A[0]=='-') {
        sexA=true;
        numa=stoi(A.substr(1,A.size()-1));
        numb=stoi(B);
    }
    else {
        sexB=true;
        numb=stoi(B.substr(1,B.size()-1));
        numa=stoi(A);
    }
    for(int i=0;i<m;i++){
        if(sexA){   //A为负
            if(find(vct[i].begin(),vct[i].end(),A)!=vct[i].end()){
                for(auto v:vct[i]){
                    if(v[0]!='-'&&v!=A) relateA[stoi(v)].first+=1.0/vct[i].size();
                }
            }
            if(find(vct[i].begin(),vct[i].end(),B)!=vct[i].end()){
                for(auto v:vct[i]){
                    if(v[0]=='-'&&v!=B) relateB[stoi(v.substr(1,v.size()-1))].first+=1.0/vct[i].size();
                }
            }
        }
        else{  //B为负
            if(find(vct[i].begin(),vct[i].end(),A)!=vct[i].end()){
                for(auto v:vct[i]){
                    if(v[0]=='-'&&v!=A) relateA[stoi(v.substr(1,v.size()-1))].first+=1.0/vct[i].size();
                }
            }
            if(find(vct[i].begin(),vct[i].end(),B)!=vct[i].end()){
                for(auto v:vct[i]){
                    if(v[0]!='-'&&v!=B) relateB[stoi(v)].first+=1.0/vct[i].size();
                }
            }
        }
    }
    sort(relateA,relateA+1000,cmp);
    sort(relateB,relateB+1000,cmp);
    bool checka=false,checkb=false;
    for(int i=0;i<1000;i++){
        if(relateA[i].first!=relateA[0].first) break;
        if(relateA[i].second==numb) {
            checka=true;
            break;
        }
    }
    for(int i=0;i<1000;i++){
        if(relateB[i].first!=relateB[0].first) break;
        if(relateB[i].second==numa) {
            checkb=true;
            break;
        }
    }
    if(checka&&checkb) cout<<A<<" "<<B;
    else{
        for(int i=0;i<1000;i++){
            if(relateA[i].first!=relateA[0].first) break;
            if(sexA) cout<<A<<" "<<relateA[i].second<<endl;
            else cout<<A<<" -"<<relateA[i].second<<endl;
        }
        for(int i=0;i<1000;i++){
            if(relateB[i].first!=relateB[0].first) break;
            if(sexB) cout<<B<<" "<<relateB[i].second<<endl;
            else cout<<B<<" -"<<relateB[i].second<<endl;
        }
    }
}

补题2:数三角形(eazy)

题意:

做法：暴力枚举*当做顶点即可，但是也不能太暴力，需要加上前缀和来判断底边那个直线，不然会一个底会被重复数很多次，非常浪费时间。写的时候也想了一下加个前缀和，但是感觉不需要，就没加前缀和了。实际上不加前缀会浪费很多时间。用了前缀和之后，每次判断底边是否全都是*,o(1)即可，否则又要遍历底边。

void solve(){           //数三角形(eazy)--遍历，遇到*就往下找-TLE -->用递归？--也是TLE ;;;遇到*就往下找-加一个前缀和
    //加一个前缀和来判断直线！！！不然会多次跑重复的，非常浪费时间
    int n,m,ans=0;     //o(n^4)会TLE， o(n^3)可以
    cin>>n>>m;
    string maze[505];
    int pre[505][505];
    for(int i=0;i<n;i++) cin>>maze[i];
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(j==0){
                if(maze[i][j]=='*') pre[i][j]=1;
                else pre[i][j]=0;
            }
            else{
                if(maze[i][j]=='*') pre[i][j]=pre[i][j-1]+1;
                else pre[i][j]=pre[i][j-1];
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(maze[i][j]=='*'){
                int l,r;
                for(int f=1;1;f++){
                    if(i+f<n&&j-f>=0&&j+f<m&&maze[i+f][j-f]=='*'&&maze[i+f][j+f]=='*') {
                        l=j-f,r=j+f;
                        if(l==0&&pre[i+f][r]==r+1) ans++;  //pre[i+f][r]==r --> ==r+1  !!!下标从0开始的
                        else if(pre[i+f][r]-pre[i+f][l-1]==r-l+1) ans++;
                    }
                    else break;
                }
            }
        }
    }
    cout<<ans<<endl;
}

补题3:漂亮数组

题意:

做法：记录一个前缀和，每次计算出当前位置前缀和时，把该位置前缀和%k，如果得出的数字是前面前缀和出现过的数字，或刚好可以%k==0。那么那个数字的后一个位置到现在这个位置就是一个合法区间 //因为一旦出现k的倍数，取余加法是有分配律的，k的倍数取余之后为0，加上前缀和会变成之前出现过的数字。再加上贪心即可得出答案。

int pre[200005];
void solve(){           //E漂亮数组--一眼感觉双指针
    // 当l,r满足时，应该立即切断。如果还往里面加东西，肯定就不是k的倍数了；除非又加了一次k的倍数进去，那么这样就会少了一个答案。(贪心)
    //NoNoNo--这个区间可能只有中间一段是可以的，前面和后面要舍弃。
    //那怎么知道前面应该舍弃多少？dp？？--不是dp
    //做法：记录一个前缀和，每次计算出当前位置前缀和时，把该位置前缀和%k，如果得出的数字是前面前缀和出现过的数字，那么那个数字的后一个位置到现在这个位置就是一个合法区间
    //因为一旦出现k的倍数，取余加法是有分配律的，k的倍数取余之后为0，加上前缀和会变成之前出现过的数字。再加上贪心即可
    int n,x,k,ans=0;
    cin>>n>>k;
    unordered_map<int,int> mp;
    for(int i=1;i<=n;i++){
        cin>>x;
        pre[i]=pre[i-1]+x;
        if(mp[pre[i]%k]||pre[i]%k==0) {
            ans++;
            pre[i]=0;       //不影响后面的，前面的数据已经没用
            mp.clear();
        }
        else mp[pre[i]%k]=1;
    }
    cout<<ans<<endl;
}

补题4:FinalCountdown

题意:

做法：这题实质上是要数每一位会发生多少次变化的总和。只要意识到这点，那么答案显而易见。例如12345，个位会变化12345次，十位会变化1234次，百位会变化123次，千位会变化12次，万位会变化1次。全部加起来即是答案。自己被样例的解释影响太深了，按照样例的想法计算，一直算不对..

注意这题的数字很大，都是字符串输入的，所以用高精度来存数字。