首页 > 代码库 > ICM Technex 2017 and Codeforces Round #400 (Div. 1 + Div. 2, combined)

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

前四题比较水,E我看出是欧拉函数傻逼题,但我傻逼不会,百度了下开始学,最后在加时的时候A掉了

AC:ABCDE Rank:182 Rating:2193+34->2227 终于橙了,不知道能待几天

 

A.A Serial Killer

题目大意:一开始给你两个字符串,每次给你当前两个串中的一个和一个新的串,用新的串换掉旧的,每次输出当前的串。(次数<=1000)

思路:二逼题

#include<iostream>
using namespace std;
int main()
{
    string a,b,c,d;int n;
    cin>>a>>b>>n;
    cout<<a<< <<b<<endl;
    while(n--)
    {
        cin>>c>>d;
        if(a==c)a=d;else b=d;
        cout<<a<< <<b<<endl;
    }
}

 

B.Sherlock and his girlfriend

题目大意:给2~n+1染色,要求任意2~n+1中的数,它的质因数(自己除外)和它颜色不同,求最小染色数和方案。(n<=100,000)

思路:质数染成一种,合数染成另一种,特判n<3的情况。

#include<cstdio>
#define MN 100000
int f[MN+5];
int main()
{
    int n,i,j;
    scanf("%d",&n);++n;
    for(i=2;i*i<=n;++i)if(!f[i])
        for(j=i*i;j<=n;j+=i)f[j]=1;
    puts(n<4?"1":"2");
    for(i=2;i<=n;++i)printf("%d ",f[i]+1);
}

 

C.Molly‘s Chemicals

题目大意:给定长度为n的数字序列和一个数k,求序列中有多少子串和为k的次幂。(n<=100,000,1<=|k|<=10)

思路:先预处理出可能用上的k的次幂(要特殊考虑k为±1),把数列前缀和,对于每个si枚举一个k的次幂,求出有多少个j<i满足si-sj=k的次幂,可以用map维护,复杂度O(nlog^2)。

#include<cstdio>
#include<iostream>
#include<map>
#define ll long long
using namespace std;
char B[1<<26],*S=B,C;int X,F;
inline int read()
{
    for(F=1;(C=*S++)<0||C>9;)if(C==-)F=-1;
    for(X=C-0;(C=*S++)>=0&&C<=9;)X=(X<<3)+(X<<1)+C-0;
    return X*F;
}
#define INF 100000000000000LL
map<ll,int> mp;
ll p[50];int pn;
int main()
{
    fread(B,1,1<<26,stdin);
    int n,k,i,j;ll x,ans=0;
    n=read();k=read();
    for(x=1;x>=-INF&&x<=INF&&!mp[x];x*=k)p[++pn]=x,mp[x]=1;
    mp.clear();
    for(i=x=0;i<n;++i)
    {
        ++mp[x];x+=read();
        for(j=1;j<=pn;++j)ans+=mp[x-p[j]];
    }
    cout<<ans;
}

 

D.The Door Problem

题目大意:N个门,门有初始状态(0/1),M个开关,每个开关可以一次性改变若干的门的开关状态,保证每个门恰被两个开关控制,求是否可能同时打开所有门。(N,M<=100,000)

思路:2-SAT裸题,每个门给对应的两个开关加上一个异或的限制关系,也可以并查集、DFS之类的,总之很水。

#include<cstdio>
char B[1<<26],*S=B,C;int X;
inline int read()
{
    while((C=*S++)<0||C>9);
    for(X=C-0;(C=*S++)>=0&&C<=9;)X=(X<<3)+(X<<1)+C-0;
    return X;
}
#define MN 100000
#define MV 200000
struct edge{int nx,t;}e[MV*2+5];
int r[MN+5],a[MN+5],b[MN+5];
int h[MV+5],en,l[MV+5],d[MV+5],cnt,z[MV+5],zn,inz[MV+5],f[MV+5],fn;
inline void ins(int x,int y)
{
    e[++en]=(edge){h[x],y};h[x]=en;
    e[++en]=(edge){h[y],x};h[y]=en;
}
void tj(int x)
{
    l[x]=d[x]=++cnt;inz[z[zn++]=x]=1;
    for(int i=h[x];i;i=e[i].nx)
    {
        if(!d[e[i].t])tj(e[i].t);
        if(inz[e[i].t]&&l[e[i].t]<l[x])l[x]=l[e[i].t];
    }
    if(l[x]==d[x])for(++fn;z[zn]!=x;inz[z[zn]]=0)f[z[--zn]]=fn;
}
int main()
{
    fread(B,1,1<<26,stdin);
    int n,m,i,j,k;
    n=read();m=read();
    for(i=1;i<=n;++i)r[i]=read();
    for(i=1;i<=m;++i)for(j=read();j--;)(a[k=read()]?b[k]:a[k])=i;
    for(i=1;i<=n;++i)
        if(r[i])ins(a[i],b[i]),ins(a[i]+m,b[i]+m);
        else ins(a[i],b[i]+m),ins(a[i]+m,b[i]);
    for(i=1;i<=m<<1;++i)if(!d[i])tj(i);
    for(i=1;i<=m;++i)if(f[i]==f[i+m])return puts("NO"),0;
    puts("YES");
}

 

E.The Holmes Children

题目大意:定义f(1)=1,f(n),n>1的值为满足x+y=n且gcd(x,y)=1的(x,y)个数;定义g(n)=Σd|n f(n/d);定义Fk(n)满足k=1时Fk(n)=f(g(n)),k>1且k mod 2=0时Fk(n)=g(Fk-1(n)),k>1且k mod 2=1时Fk(n)=f(Fk-1(n)) 。给出n,k,求Fk(n)mod 1000000007。(1<=n,k<=10^12)

思路:f(n)等同于求满足gcd(x,n-x)=1的x的个数,又因为gcd(x,n-x)=gcd(x,n),所以f(n)就是phi(n)。通过观察发现g(n)=n,所以Fk(n)就是对n做(k+1)/2遍phi。每次n^0.5暴力,n=1时停止就可以了,因为n>2时,phi(n)必为偶数,偶数的phi又必然减少一半,所以复杂度大约是O(n^0.5*logn)。

#include<iostream>
using namespace std;
#define ll long long
#define MX 1000000
ll f[MX+5];
ll F(ll x)
{
    if(x<=MX)return f[x];
    ll i,r=x;
    for(i=2;i*i<=x;++i)if(x%i==0)
    {
        r=r/i*(i-1);
        while(x%i==0)x/=i;
    }
    return x>1?r/x*(x-1):r;
}
int main()
{
    ll n,k,i,j;
    cin>>n>>k;k=k+1>>1;
    for(i=1;i<=MX;++i)f[i]=i;
    for(i=2;i<=MX;i+=2)f[i]>>=1;
    for(i=3;i<=MX;i+=2)if(f[i]==i)
        for(j=i;j<=MX;j+=i)f[j]=f[j]/i*(i-1);
    while(n>1&&k--)n=F(n);
    cout<<n%1000000007;
}

 

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