2020 智算之道高校组初赛第一场

排队

一看数据直接暴力过，时间复杂度O(m*n),如果 i 是 m 个数的倍数，直接修改标记，统计一下修改标记的数据有多少个，最后 n - 修改标记的数的个数就是我们要的答案。

#include <cstdio>
#include <algorithm>
#define rep(i,a,b) for(auto i=a;i<=b;++i)
using namespace std;
int a[110];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;++i) scanf("%d",&a[i]);
    int res=0;
    for(int i=1;i<=n;++i)
    {
        int ok=0;
        for(int j=0;j<m;++j)
            if(i%a[j]==0) ok=1;
        if(ok) res++;
    }
    printf("%d\n",n-res);
    return 0;
}

开关

贪心的做法，从后往前处理，当遇到第一个 1 时修改标记，答案res++，然后前面的 0 变 1，1 变 0，此时修改标记后当遇到第一个 0 时，标记改回去，答案 res++，如此往复，直到遍历完整个字符串。时间复杂度是O(N)

#include <iostream>
#include <algorithm>
#define rep(i,a,b) for(auto i=a;i<=b;++i)
using namespace std;
int a[110],n;
string s;
int main()
{
    cin>>n>>s;
    int res=0,ok=1;
    for(int i=n-1;i>=0;--i){
        if(s[i]=='1'&&ok) res++,ok=0;
        if(s[i]=='0'&&!ok) res++,ok=1;
    }
    cout<<res<<endl;
    return 0;
}

字符串

字符串 hash 去重，找 s.size() 长度的子串，看与 s 的字符组成是否相同，如果相同，则 res++，最后输出答案。

#include <iostream>
#include <map>
#include <cstring>
using namespace std;
const int maxn=1e5+7,base=131;
string s,t,ss;
typedef unsigned long long ULL;
map<ULL,int>Cnt;
ULL h[maxn],P[maxn];
int a[30],b[30];
ULL get(int l,int r)
{
    return h[r]-h[l-1]*P[r-l+1];
}
int main()
{
    cin>>s>>t;
    int s1=s.size(),t1=t.size();
    for(int i=0;i<s1;++i) a[s[i]-'a']++;
    P[0]=1;
    for(int i=1;i<=t1;++i)
    {
        P[i]=P[i-1]*base;
        h[i]=h[i-1]*base+t[i-1];
        if(i>=s1)
        {
            ULL tmp=get(i-s1+1,i);
            Cnt[tmp]++;
        }
    }
    int res=0;
    for(map<ULL,int>::iterator it=Cnt.begin();it!=Cnt.end();it++)
    {
        ss.clear();
        ULL t=it->first;
        while(t)
        {
            ss+=t%131;
            t/=131;
        }
        int len=ss.size();
     //   cout<<ss<<endl;
        memset(b,0,sizeof(b));
        int ok=1;
        for(int i=0;i<len;++i) b[ss[i]-'a']++;
        for(int i=0;i<27;++i)
            if(a[i]!=b[i]) ok=0;
        if(ok) res++;
    }
    cout<<res<<'\n';
    return 0;
}

**由于字符串哈希的时候把str[i-1]写成了str[i]导致只过了百分之30的数据，下面是打codeforces认识的一个大佬写的AC代码，理论上我认为我自己AC了**~~hhh，不要说我厚脸皮哈~~

#pragma GCC optimize(2)
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const int mod = 1e9+7;
const double eps = 1e-5;
const int N = 2e5 + 10;

void redirect() {
    #ifdef LOCAL
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
}

char s[N], t[N];
int cnt[27], ccnt[27];
int ans = 0;

ull seed = 131;
ull pw[N], hs[N];
vector<ull> fin;

inline ull cal(int l, int r) {
    return (ull)(hs[r] - hs[l-1] * pw[r-l+1]);
}

void check(int l, int r) {
    bool f = true;
    for (int i=0; i<26; i++) {
        if (cnt[i]!=ccnt[i]) {
            f = false;
            break;
        }
    }
    if (f) {
        fin.push_back(cal(l,r));
    }
}

int main() {
    //redirect();

    s[0] = t[0] = '0';
    scanf("%s", s+1);
    scanf("%s", t+1);
    
    int len1 = strlen(s);
    int len2 = strlen(t);

    for (int i=1; i<len1; i++) {
        cnt[s[i]-'a'] ++;
        ccnt[t[i]-'a'] ++;
    }

    pw[0] = 1;
    for (int i=1; i<=len2; i++) {
        pw[i] = pw[i-1] * seed;
        hs[i] = hs[i-1] * seed + t[i] - 'a';
    }

    check(1,len1-1);
    for (int i=len1; i<len2; i++) {
        ccnt[t[i-len1+1]-'a'] --;
        ccnt[t[i]-'a'] ++;
        check(i-len1+2, i);
    }
    
    sort(fin.begin(), fin.end());
    ans = fin.size();
    for (int i=1; i<fin.size(); i++) {
        if (fin[i-1] == fin[i]) {
            ans --;
        }
    }
    printf("%d\n", ans);
    return 0;
}