2020 지산의 길 1차전 문제풀이

A, B는 모두 위조 코드이다
A. 줄 서기:
물문제죠. 하지만 조금 최적화할 수 있어요.

/**
Code：
**/
read(n)
for(int i=1;i<=n;i++) read(a[i])
for(int i=1;i<=m;i++){
       if(!vis[a[i]]{
        for(int i=1;i<=n;i++){
        vis[k] = 1;
        }
    }
}
ll ans = 0;
for(int i=1;i<=n;i++){
    if(!vis[i]) ans++;
}
out(ans)

B. 스위치:
뒤에서 앞으로 고려하다
그 다음에 비트 연산으로 최적화를 고려합니다.
rk1의 0ms가 어떻게 왔는지 귀신이 알아.

scanf("%s",s+1);
int cot = 0,ans = 0;
for(int i=1;i<=len;i++){
    int x = s[i]-'0';
    x^=cot;
    if(x){
        ans++;
        cot^=1;
    }    
}
out(ans)

C. 문자열:
우선 s열이 t열에 있는 위치를 고려합니다
그래서 t의 모든 문자를 매거하여 s의 시작 위치로 삼으면 모든 자모의 출현 횟수가 같다고 판단하면 된다
이후 이 하위 문자열이 나타났는지 판단하면 맵에서 당연히 다시 그룹 크기로 줄일 수 있습니다
최종 최적화:
슬라이딩 창을 사용하여 O (n) 로 최적화
rk1 이 0ms 진짜 귀신
Code:

/*** keep hungry and calm CoolGuang!***/
#pragma GCC optimize(2)
#include 
#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair pp;
const ll INF=1e17;
const int Maxn=2e7+10;
const int maxn =2e5+10;
const int mod=998244353;
const int Mod = 1e9+7;
const double eps=1e-3;
inline bool read(ll &num)
{char in;bool IsN=false;
    in=getchar();if(in==EOF) return false;while(in!='-'&&(in'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p;
char s[maxn],t[maxn];
ll sum[maxn][30];
int vis[30],tvis[30];
bool mp1[Maxn],mp2[Maxn];
ull H[maxn],H1[maxn];
char F[300];
inline void out(ll x){ if (x == 0) return (void) (putchar('0'));    ll tmp = x > 0 ? x : -x;    if (x < 0) putchar('-');    int cnt = 0;    while (tmp > 0) {        F[cnt++] = tmp % 10 + '0';        tmp /= 10;     }   while (cnt > 0) putchar(F[--cnt]);   printf("
"); }
ll qpow(ll a,ll b){
    ll ans = 1;
    while(b){
        if(b&1) ans = (ans*a)%mod;
        b/=2;a = (a*a)%mod;
    }return ans;
}
int main(){
    scanf("%s%s",s+1,t+1);
    int lens = strlen(s+1),lent = strlen(t+1);
    for(register int i=1;i<=lens;i++) vis[s[i]-'a']++;
    ll temp_27 = qpow(27,lens);
    ll ans = 0;
    for(register int i=1;i<=lent;i++) H[i] = (H[i-1]*27 + (t[i]-'a'+1))%mod;
    for(int i=1;i<=lens;i++) tvis[t[i]-'a']++;
    int cot = 0;
    for(int i=0;i<26;i++) if(tvis[i] != vis[i]) cot++;
    for(register int i=lens;i<=lent;i++){
        if(!cot){
            ll tempx = (H[i] - (H[i-lens]*temp_27)%mod+mod)%mod;
            tempx %= 10000007;
            if(!mp1[tempx]){
                mp1[tempx] = true;
                ans++;
            }
        }
        tvis[t[i-lens+1]-'a']--;
        if(tvis[t[i-lens+1]-'a'] == vis[t[i-lens+1]-'a']&&tvis[t[i-lens+1]-'a']+1 != vis[t[i-lens+1]-'a']) cot--;
        if(tvis[t[i-lens+1]-'a'] != vis[t[i-lens+1]-'a']&&tvis[t[i-lens+1]-'a']+1 == vis[t[i-lens+1]-'a']) cot++;
        tvis[t[i+1]-'a']++;
        if(tvis[t[i+1]-'a'] == vis[t[i+1]-'a']&&tvis[t[i+1]-'a']-1 != vis[t[i+1]-'a']) cot--;
        if(tvis[t[i+1]-'a'] != vis[t[i+1]-'a']&&tvis[t[i+1]-'a']-1 == vis[t[i+1]-'a']) cot++;
    }
    out(ans);
    return 0;
}
/**
aab
abacabaa
**/

마지막 rk6..파이팅!