map | kugwzk's space

雪崩啊。。。FST了两题数组下标打错。。

A. A Serial Killer

#include <bits/stdc++.h>

using namespace std;
string s,t;
int n;
int main()
{
    cin>>s>>t;
    cout<<s<<" "<<t<<endl;
    scanf("%d",&n);
    while(n--){
        string tmp1,tmp2;cin>>tmp1>>tmp2;
        if(tmp1==s) {s=tmp2;cout<<s<<" "<<t<<endl;}
        else {t=tmp2;cout<<s<<" "<<t<<endl;}
    }
}

#include <bits/stdc++.h>

using namespace std;

string s,t;

int n;

int main()

{

cin>>s>>t;

cout<<s<<" "<<t<<endl;

scanf("%d",&n);

while(n--){

string tmp1,tmp2;cin>>tmp1>>tmp2;

if(tmp1==s) {s=tmp2;cout<<s<<" "<<t<<endl;}

else {t=tmp2;cout<<s<<" "<<t<<endl;}

}

B. Sherlock and his girlfriend

随便构造一下，合数为2，质数为1就好了。

#include <bits/stdc++.h>
#define maxn 100010
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
bool isprime[maxn];
int prime[maxn],num_prime;
void getprime(ll n)
{
    memset(isprime,true,sizeof(isprime));
    isprime[0]=0,isprime[1]=0;
    for(int i=2;i<n;i++){
        if(isprime[i])
            prime[num_prime++]=i;
        for(int j=0;j<num_prime&&prime[j]*i<n;j++){
            isprime[i*prime[j]]=false;
            if(i%prime[j]==0)
                break;
        }
    }
}
int n;
int vis[maxn];
int main()
{
    getprime(100010);
    scanf("%d",&n);
    for(int i=2;i<=n+1;i++){
        if(isprime[i]) {
            vis[i]=1;
        }
        else vis[i]=2;
    }
    if(n!=1&&n!=2)
        printf("%d\n",2);
    else puts("1");
    for(int i=2;i<=n+1;i++) {
        if(i!=2) printf(" ");
        printf("%d",vis[i]);
    }
}

#include <bits/stdc++.h>

#define maxn 100010

#define inf 0x3f3f3f3f

using namespace std;

typedef long long ll;

bool isprime[maxn];

int prime[maxn],num_prime;

void getprime(ll n)

{

memset(isprime,true,sizeof(isprime));

isprime[0]=0,isprime[1]=0;

for(int i=2;i<n;i++){

if(isprime[i])

prime[num_prime++]=i;

for(int j=0;j<num_prime&&prime[j]*i<n;j++){

isprime[i*prime[j]]=false;

if(i%prime[j]==0)

break;

}

int n;

int vis[maxn];

int main()

{

getprime(100010);

scanf("%d",&n);

for(int i=2;i<=n+1;i++){

if(isprime[i]) {

vis[i]=1;

}

else vis[i]=2;

}

if(n!=1&&n!=2)

printf("%d\n",2);

else puts("1");

for(int i=2;i<=n+1;i++) {

if(i!=2) printf(" ");

printf("%d",vis[i]);

}

C. Molly’s Chemicals

题意：给出n个数字a[]和一个k，求区间和为k的次幂的区间有多少个。N<=1e5，1<=|k|<=10,-1e9<a[i]<1e9。

因为区间和最大为1e14，最小为-1e14，所以这个k的次幂的指数大概不会超过50.把所有的在范围内的K次幂全部算出来。然后维护一个前缀和，把搞过的前缀和放到map里面去。对于每个前缀和都减去一个k次幂的数看是否在Map里能找到就可以了。

#include <bits/stdc++.h>
#define maxn 100010
using namespace std;
typedef long long ll;
const ll inf=100000000000000LL;
int n,k,a[maxn];
ll sum[maxn],kk[maxn];
map<ll,int>ma;
int main()
{
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        sum[i]=sum[i-1]+a[i];
    }
    kk[0]=1;
    int cnt=1;
    if(abs(k)!=1){
        for(int i=1;;i++){
            kk[i]=kk[i-1]*k;
            if((kk[i]*k>0&&kk[i]*k>inf)||(kk[i]*k<0&&kk[i]*k<-inf)) break;
            cnt++;
        }
    }
    else{
        if(k==-1) {cnt=1;kk[1]=-1;}
        else cnt=0;
    }
    ll ans=0;
    ma[0]=1LL;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=cnt;j++){
            ll tmp2=sum[i]-kk[j];
            if(ma.count(tmp2)) ans+=(ll)ma[tmp2];
        }
        ma[sum[i]]++;
    }
    printf("%I64d\n",ans);
}

#include <bits/stdc++.h>

#define maxn 100010

using namespace std;

typedef long long ll;

const ll inf=100000000000000LL;

int n,k,a[maxn];

ll sum[maxn],kk[maxn];

map<ll,int>ma;

int main()

{

scanf("%d %d",&n,&k);

for(int i=1;i<=n;i++){

scanf("%d",&a[i]);

sum[i]=sum[i-1]+a[i];

}

kk[0]=1;

int cnt=1;

if(abs(k)!=1){

for(int i=1;;i++){

kk[i]=kk[i-1]*k;

if((kk[i]*k>0&&kk[i]*k>inf)||(kk[i]*k<0&&kk[i]*k<-inf)) break;

cnt++;

}

else{

if(k==-1) {cnt=1;kk[1]=-1;}

else cnt=0;

}

ll ans=0;

ma[0]=1LL;

for(int i=1;i<=n;i++){

for(int j=0;j<=cnt;j++){

ll tmp2=sum[i]-kk[j];

if(ma.count(tmp2)) ans+=(ll)ma[tmp2];

}

ma[sum[i]]++;

}

printf("%I64d\n",ans);

}

D. The Door Problem

题意：有n个门，m个开关，每个门被两个开关控制。给出n个门的初始状态，然后给出每个开关可以控制哪些门。让你判断能否通过操作，可以让所有的门打开。n,m<=1e5

因为每个门都是被两个开关控制，那么把钥匙看成点，门看成边，如果某个门的状态为1，那么也就意味着它所连的两个钥匙必须都选或者都不选。也就是这条边两端的颜色要一样。如果某个门的状态为0，那么他连的两个钥匙必须要只选择一个。也就是这条边两端的颜色不一样。这样建完图后会有一个个连通块，如果每个连通块二染色不会出现矛盾，那么就是可行。否则无解。。。

#include <bits/stdc++.h>
#define maxn 100010
#define mp make_pair
#define inf 0x3f3f3f3f
#define REP(i,x,y) for(int i=x;i<y;i++)
#define dbg(x) cout<<#x<<" = "<<(x)<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int n,m;
vector<pii>e[maxn];
int vis[maxn],p[maxn],c[maxn],vis2[maxn];
struct P{
    int v,col;
    P(){}
    P(int _v,int _c):v(_v),col(_c){}
};
bool bfs(int st,int col){

    c[st]=col;vis2[st]=1;
    queue<P>que;que.push(P(st,col));
    while(!que.empty()){
        P now=que.front();que.pop();
        int Size=e[now.v].size();
        REP(i,0,Size){
            pii Next=e[now.v][i];int tmp=Next.second;
            int tmp2=(tmp==1 ? now.col: !now.col);
            if(c[Next.first]!=-1){
                if(c[Next.first]!=tmp2) return false;
                else continue;
            }
            else c[Next.first]=tmp2;
            vis2[Next.first]=1;
            que.push(P(Next.first,tmp2));
        }
    }
    return true;
}
int main()
{
    scanf("%d %d",&n,&m);
    REP(i,1,n+1) scanf("%d",&vis[i]);
    REP(i,1,m+1){
        int cnt;scanf("%d",&cnt);
        REP(j,1,cnt+1){
            int u;scanf("%d",&u);
            if(!p[u]) p[u]=i;
            else {
                e[i].push_back(mp(p[u],vis[u]));
                e[p[u]].push_back(mp(i,vis[u]));
            }
        }
    }
    int flag=1;
    memset(c,-1,sizeof(c));
    REP(i,1,m+1){
        if(!vis2[i]) flag=bfs(i,1);
        if(!flag) break;
    }
    if(flag) puts("YES");
    else puts("NO");
}

#include <bits/stdc++.h>

#define maxn 100010

#define mp make_pair

#define inf 0x3f3f3f3f

#define REP(i,x,y) for(int i=x;i<y;i++)

#define dbg(x) cout<<#x<<" = "<<(x)<<endl;

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

int n,m;

vector<pii>e[maxn];

int vis[maxn],p[maxn],c[maxn],vis2[maxn];

struct P{

int v,col;

P(){}

P(int _v,int _c):v(_v),col(_c){}

};

bool bfs(int st,int col){

c[st]=col;vis2[st]=1;

queue<P>que;que.push(P(st,col));

while(!que.empty()){

P now=que.front();que.pop();

int Size=e[now.v].size();

REP(i,0,Size){

pii Next=e[now.v][i];int tmp=Next.second;

int tmp2=(tmp==1 ? now.col: !now.col);

if(c[Next.first]!=-1){

if(c[Next.first]!=tmp2) return false;

else continue;

}

else c[Next.first]=tmp2;

vis2[Next.first]=1;

que.push(P(Next.first,tmp2));

}

return true;

}

int main()

{

scanf("%d %d",&n,&m);

REP(i,1,n+1) scanf("%d",&vis[i]);

REP(i,1,m+1){

int cnt;scanf("%d",&cnt);

REP(j,1,cnt+1){

int u;scanf("%d",&u);

if(!p[u]) p[u]=i;

else {

e[i].push_back(mp(p[u],vis[u]));

e[p[u]].push_back(mp(i,vis[u]));

}

int flag=1;

memset(c,-1,sizeof(c));

REP(i,1,m+1){

if(!vis2[i]) flag=bfs(i,1);

if(!flag) break;

}

if(flag) puts("YES");

else puts("NO");

}

E. The Holmes Children

题意：略。。太长了。。

首先(x,y)满足x+y=n和gcd(x,y)=1的话，那么gcd(x+y,y)=1，所以gcd(n,y)=1.所以满足的y就是 $\phi(n)$ 。这个反证法证一证就好了。。。f(n)= $\phi(n)$ 。

然后g()那个函数就是g(n)=n。

然后我们就需要求一个 $\phi( \phi(\phi(.... \phi(n))))$ 这样的东西，大概是(k+1)/2左右。而这个暴力算logn次就变成1了。。。

#include <bits/stdc++.h>
#define mod 1000000007
#define inf 1e13
using namespace std;
typedef long long ll;
ll n,k;
ll phi(ll n){
    ll ans=n;
    for(ll i=2;i*i<=n;i++){
        if(n%i==0){
            ans=ans/i*(i-1);
            while(n%i==0) n/=i;
        }
    }
    if(n>1) ans=ans/n*(n-1);
    return ans;
}
int main()
{
    scanf("%I64d %I64d",&n,&k);
    ll ans=n;
    for(ll i=1LL;i<=k;i++){
        if(i%2) ans=phi(ans);
        if(ans==1) break;
    }
    printf("%I64d\n",ans%mod);
}

#include <bits/stdc++.h>

#define mod 1000000007

#define inf 1e13

using namespace std;

typedef long long ll;

ll n,k;

ll phi(ll n){

ll ans=n;

for(ll i=2;i*i<=n;i++){

if(n%i==0){

ans=ans/i*(i-1);

while(n%i==0) n/=i;

}

if(n>1) ans=ans/n*(n-1);

return ans;

}

int main()

{

scanf("%I64d %I64d",&n,&k);

ll ans=n;

for(ll i=1LL;i<=k;i++){

if(i%2) ans=phi(ans);

if(ans==1) break;

}

printf("%I64d\n",ans%mod);

}

题目链接

题意：给出2*n个字符串，前n个为一组，后n个为一组。问在两组中都出现的字符串有几个。

map瞎搞搞也可以做，但是为了学一下字符串的双hash，所以我写了hash。

直接把每个字符串hash一下，map记一下数。

#include <bits/stdc++.h>
#define mod1 1000000007
#define mod2 998244353
#define H 131
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
char s[22];
map<pii,int> ma;
int n,cnt;
int get_hash(char s[],int mod){
    ll res=0;int len=strlen(s+1);
    for(int i=1;i<=len;i++)
        res=(res*H%mod+s[i])%mod;
    return res%mod;
}
int main()
{
    while(scanf("%d",&n)!=EOF){
        cnt=0;ma.clear();
        for(int i=1;i<=n;i++){
            scanf("%s",s+1);
            pii res=make_pair(get_hash(s,mod1),get_hash(s,mod2));
            ma[res]++;
        }
        for(int i=1;i<=n;i++){
            scanf("%s",s+1);
            pii res=make_pair(get_hash(s,mod1),get_hash(s,mod2));
            if(!ma[res]) continue;
            else{
                ma[res]--;
                cnt++;
            }
        }
        printf("%d\n",cnt);
    }
}

#include <bits/stdc++.h>

#define mod1 1000000007

#define mod2 998244353

#define H 131

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

char s[22];

map<pii,int> ma;

int n,cnt;

int get_hash(char s[],int mod){

ll res=0;int len=strlen(s+1);

for(int i=1;i<=len;i++)

res=(res*H%mod+s[i])%mod;

return res%mod;

}

int main()

{

while(scanf("%d",&n)!=EOF){

cnt=0;ma.clear();

for(int i=1;i<=n;i++){

scanf("%s",s+1);

pii res=make_pair(get_hash(s,mod1),get_hash(s,mod2));

ma[res]++;

}

for(int i=1;i<=n;i++){

scanf("%s",s+1);

pii res=make_pair(get_hash(s,mod1),get_hash(s,mod2));

if(!ma[res]) continue;

else{

ma[res]--;

cnt++;

}

printf("%d\n",cnt);

}

kugwzk's space

曾经的acmer

标签归档：map

ICM Technex 2017 and Codeforces Round #400 (Div. 1 + Div. 2, combined)做题记录

BZOJ 2761: [JLOI2011]不重复数字（map）

Description

Input

Output

Sample Input

Sample Output

uvalive 6959 Judging Troubles（双hash模板题）