F.序列

北航第十一届程序设计竞赛网络预赛题解

比赛链接：

官方题解

A.模式

对于窝这个外校成员，这道题好麻烦啊= =

不过我发现我可以点开别的用户的ID，看到学号。

然后再猜一猜，就知道了计算机系应该是XX06XXXX,软件学院是XX21XXXX

代码

#include
    
     #include
     
      using namespace std;string s;int main(){    while(cin>>s)    {        if(s[2]=='0'&&s[3]=='6')            cout<<"SCSE"<
     
    

B.并联变阻器

题意即统计满足a,b≤N且aba+b是整数的二元组(a,b)的个数，条件也即a,b≤N且(a+b)|ab。

令r=gcd(a,b)，则有gcd(ar,br)=1，再令a=rx,b=ry，那么(a+b)|ab 可以表示为r(x+y)|r2xy，也就是(x+y)|rxy。

由于x与y互质，所以gcd(x+y,x)=gcd(x+y,y)=gcd(x,y)=1，(x+y)与x,y也是互质的，则必然有(x+y)|r。

令r=k(x+y)，则a=kx(x+y),b=ky(x+y)，可以发现a,b≤N对应着x,y≤N−−√，只需要枚举不超过N−−√的互质数对(x,y)，即可计算出对应的每一组解，这样做的时间复杂度是O(N−−√2)=O(N)的，其中求最大公约数的部分可以通过预处理达到O(1)。

注意到本题的数据组数较大，单组数据使用O(N)算法也会超时，但是枚举所有解的时候也确定了这组解是属于N≥max(a,b)的所有N，所以将这组(a,b)统计到对应的max(a,b)，再求一遍前缀和即可得到所有答案，预处理复杂度O(N)，单点查询O(1)。

代码

#include 
    
     using namespace std;const int maxn = 1e6;int vis[maxn + 50] ,p[maxn + 50],sum[maxn + 50];int quick_pow(int x , int y){    int res=1;    while(y){        if(y&1) res*=x;        x*=x;        y>>=1;    }    return res;}int main(){    for(int i = 1 ; i <= maxn ; ++ i)        p[i] = 1;    for(int i = 2 ; i <= maxn ; ++ i)        if(!vis[i]){            for(int j = i ; j <= maxn ; j += i){                vis[j] = 1;                int t = 0 , x = j;                while(x % i == 0) x/=i , t ++ ;                t=t>>1;                p[j]*=quick_pow( i , t );            }        }    for(int i = 1 , a , b ; i <= maxn ; ++ i){        int y = i / p[i] , z = i / p[i] / p[i];        for(int j = 1 ; ((a = i + y * j) <= maxn) && ((b = j*y + j * j * z) <= maxn) ; ++ j) sum[max(a,b)]++;    }    for(int i = 1 ; i <= maxn ; ++ i) sum[i] += sum[i-1];    int n ;    while(~scanf("%d",&n)) printf("%d\n",sum[n]);    return 0;}
    

D.最大公约数

贪心。

首先要意识到，最后答案每一段的GCD，一定和整个的GCD是一样的。

所以就直接扫一遍就好了。

代码

#include
    
     #include
     
      using namespace std;#define maxn 100005int a[maxn];int gcd(int A,int B){    if(B==0)return A;    return gcd(B,A%B);}int main(){    int n;    while(scanf("%d",&n)!=EOF)    {        for(int i=1;i<=n;i++)            scanf("%d",&a[i]);        int Ans = a[1];        for(int i=1;i<=n;i++)            Ans = gcd(Ans,a[i]);        int ans = 0;        int tmp = 0;        for(int i=1;i<=n;i++)        {            if(tmp == 0)                tmp = a[i];            tmp = gcd(tmp,a[i]);            if(tmp == Ans)            {                ans++;                tmp = 0;            }        }        printf("%d\n",ans);    }}
     
    

E.矩阵

就给你2500个方程，一共有100个未知数，然后每个方程里面只有两个未知数，每个未知数的系数都是1,

问你这个方程是否存在一组解。

大概一眼看到的算法大概就是算一下矩阵的秩，判断他和增广矩阵的秩是否相同就好了

然而窝TLE了= =

所以还是老老实实写差分约束吧，按照差值建边之后，再跑spfa，判断是否有负环就好了

我的判断方法比较偷懒，因为spfa有负环的话，会一直跑下去，所以我只要判断他是否会一直跑下去就好了

代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define maxn 110vector
         
          
            > E[maxn];int vis[maxn];int inq[maxn];int d[maxn];int main(){ int n,m,k; while(cin>>n>>m>>k) { int flag = 0; for(int i=0;i