2020年常熟理工学院第一届线上ACM选拔赛解题报告

2020年常熟理工学院第一届线上ACM选拔赛-by bob_teacher

本次题目难度顺序基本从难到易,在这里非常感谢出题组同学的真情付出。此博客原文地址:https://www.cnblogs.com/BobHuang/p/12610795.html

1.6195: Trojke II

这个题目是4140: Trojke的一个扩展,在这个题目里由于可以匹配的棋子很多,我们应该想的是去遍历这个棋盘的所有线。这就是格点问题:从(0,0)到(x,y)的线段,经过的格点数目是gcd(x,y)+1。比如(3,5)是两个;(2,4)就是3个,因为过了(1,2);(8,20)是5个,因为还过了(2,5)、(4,10)、(6,15)。这个的证明可以从相似三角形下手,比较简单。
所以这个题目我们预处理出所有的线就可以了,具体实现思路可以看代码。我们可以查一条线上的点的个数x,然后C(x,3)就是当前点构成三胞胎的个数。
复杂度分析:
直接三个字符求解
m * m * m 如果满数据就是n^6=1e12
考虑所有的斜线,就是已知100以内互质对数 *n*n
100以内互质对数为6087,实际可能的是1547(优化过的)
1547 * n * n = 1e7,当然还有常数,但是足够通过这个题目

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=105;
const int M=1e4+5;
char s[N][N];
int a[N<<1],b[N<<1],c[N<<1],d[N<<1];
int ma[4][M<<1];
vector<int> v[4];
ll cal(int x) {
   if(x<3) return 0;
   return 1LL*x*(x-1)*(x-2)/6;
}
int main() {
   //freopen("in.txt","r",stdin);
   int n;
   scanf("%d",&n);
   for(int i=0;i<n;i++) {
       scanf("%s",s[i]);
   }
   vector<pair<int,int> > vec;
   for(int i=0;i<n;i++) {
       for(int j=0;j<n;j++) {
           if(s[i][j]=='.') continue;
           //如果不是'.',a统计主对角线,b统计副对角线,c统计行,j统计列
           a[i-j+n]++,b[i+j]++,c[i]++,d[j]++;
           //记录当前点
           vec.push_back({i,j});
       }
   }
   ll ans=0;
   for(int i=0;i<n<<1;i++) {
       //对这四个进行统计
       ans+=cal(a[i])+cal(b[i])+cal(c[i])+cal(d[i]);
   }
   //循环剩下的需要格点
   for(int i=1;i<=n;i++) {
       for(int j=i+1;j<=n;j++) {
           if(__gcd(i,j)!=1) continue;
           //访问当前点
           for(int k=0;k<vec.size();k++) {
               int x=vec[k].first,y=vec[k].second;
               ma[0][x*i+y*j]++;ma[1][x*i-y*j+M]++;
               ma[2][y*i+x*j]++,ma[3][y*i-x*j+M]++;
               if(ma[0][x*i+y*j]==1) v[0].push_back(x*i+y*j);
               if(ma[1][x*i-y*j+M]==1) v[1].push_back(x*i-y*j+M);
               if(ma[2][y*i+x*j]==1) v[2].push_back(y*i+x*j);
               if(ma[3][y*i-x*j+M]==1) v[3].push_back(y*i-x*j+M);
           }
           //四层为四个对应的方向
           for(int k=0;k<4;k++) {
               for(int l=0;l<v[k].size();l++) {
                   ans+=cal(ma[k][v[k][l]]);
                   ma[k][v[k][l]]=0;
               }
               v[k].clear();
           }
       }
   }
   printf("%I64d\n",ans);
   return 0;
}

出题人的代码
预处理欧拉,枚举所有欧拉再枚举点,用的dp转移

#include<bits/stdc++.h>
using namespace std;

vector<int>f[205];
char G[105][105];
int dp1[105][105],dp2[105][105];
void PhiTable(int n){
   for(int i=2;i<=n;i++){
       for(int j=1;j<i;j++)
           if(__gcd(i,j)==1)
               f[i].push_back(j);
   }
}
int main(){
   int n,sum=0;
   scanf("%d",&n);
   for(int i=1;i<=n;i++)scanf("%s",G[i]+1);
   int up=2*n-2;
   PhiTable(up);
   for(int k=1;k<=up;k++){
       if(k==1){
           //row and col
           for(int i=1;i<=n;i++)
               for(int j=1;j<=n;j++){
                   if(dp1[i-1][j]>=2&&G[i][j]!='.')sum+=dp1[i-1][j]*(dp1[i-1][j]-1)/2;
                   dp1[i][j]=dp1[i-1][j]+(G[i][j]!='.');
                   if(dp2[i][j-1]>=2&&G[i][j]!='.')sum+=dp2[i][j-1]*(dp2[i][j-1]-1)/2;
                   dp2[i][j]=dp2[i][j-1]+(G[i][j]!='.');
                   //printf("i=%d j=%d 1 %d\n",i,j,sum);
               }
           continue;
       }
       for(int l=0;l<f[k].size();l++){
           for(int i=1;i<=n;i++)
               for(int j=1;j<=n;j++)
                   dp1[i][j]=dp2[i][j]=(G[i][j]!='.');
           for(int i=1+f[k][l];i<=n;i++){
               int x=i-f[k][l];
               for(int j=1;j<=n-k+f[k][l];j++){
                   int y1=j+k-f[k][l];
                   if(dp1[x][y1]>=2&&G[i][j]!='.')sum+=dp1[x][y1]*(dp1[x][y1]-1)/2;
                   dp1[i][j]=dp1[x][y1]+(G[i][j]!='.');
                   //printf("upx=%d upy=%d dp1=%d 1(%d,%d) sum=%d\n",x,y1,dp1[x][y1],i,j,sum);
               }
               for(int j=1+k-f[k][l];j<=n;j++){
                   int y2=j-k+f[k][l];
                   if(dp2[x][y2]>=2&&G[i][j]!='.')sum+=dp2[x][y2]*(dp2[x][y2]-1)/2;
                   dp2[i][j]=dp2[x][y2]+(G[i][j]!='.');
                   //printf("upx=%d upy=%d 2(%d,%d) sum=%d\n",x,y2,i,j,sum);
               }
           }
       }
   }
   printf("%d\n",sum);
   return 0;
}

另一份验题代码

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
vector<pair<int, int>> V;
int n, ans;
string s[100];
bool vis[100][100];
inline int cal(int cnt)
{
   return cnt >= 3 ? cnt * (cnt - 1) * (cnt - 2) / 6 : 0;
}
inline int add(int i, int j, int ai, int aj)
{
   int cnt = 0;
   while (j < n&&i < n )
   {
       vis[i][j] = true;
       if (s[i][j] != '.')
           cnt++;
       i += ai, j += aj;
   }
   return cal(cnt);
}
inline int sub(int i, int j, int ai, int aj)
{
   int cnt = 0;
   while (j >= 0&&i < n )
   {
       vis[i][j] = false;
       if (s[i][j] != '.')
           cnt++;
       i += ai, j -= aj;
   }
   return cal(cnt);
}
int main()
{
#ifdef bob
   freopen("data1.in", "r", stdin);
   int nol_cl = clock();
#endif
   cin >> n;
   cin.get();
   for (int i = 0; i < n; i++)
       getline(cin, s[i]);
   for (int i = 1; i <= n; i++)
   {
       for (int j = 1; j <= n; j++)
       {
           //min(n *1./ i, n*1. / j)为最多有几个点是优化
           if (__gcd(i, j) == 1 && min(n *1./ i, n*1. / j) > 2)
           {
               V.push_back({i, j});
           }
       }
   }
   //cpp11写法,循环访问V
   for (auto X : V)
   {
       for (int i = 0; i < n; i++)
       {
           for (int j = 0; j < n; j++)
           {
               if (!vis[i][j])
               {
                      //左上到右下
                   ans += add(i, j, X.fi, X.se);
               }
           }
       }
       for (int i = 0; i < n; i++)
       {
           for (int j = 0; j < n; j++)
           {
               if (vis[i][j])
               {
                   //左下到右上
                   ans += sub(i, j, X.fi, X.se);
               }
           }
       }
   }
   //每一行
   for (int i = 0, j = 0; j < n; j++)
   {
       ans += add(i, j, 1, 0);
   }
   //每一列
   for (int i = 0, j = 0; i < n; i++)
   {
       ans += add(i, j, 0, 1);
   }
   cout << ans << "\n";
#ifdef bob
   LOG("Time: %dms\n", int((clock() - nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
   return 0;
}

2.6197: 最好一样

这个是位运算的题目,这是“按位或”运算符,||是逻辑或,两个相应的二进制位中只要有一个为1,该位的结果值为1,即有1得1。曾经写过一个operator的理解,有兴趣可以看看。
我们可以以当前数字作为下标进行统计个数。或会让这个数字变大(有些位上多1),所以我们从小的数字开始枚举,如果或的值不为i,说明异或的新值可以多a[i]个,当前清空,如果这个数字恰巧只有一个,那只能当读出现了,统计下来。
update: 要么a[i]不或m,要么或m,如果存在显然或m,这样会减少。一个数字或上两次并不会变得更大,所以一次处理也可以。


#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int N=2e5+5;
int a[N];
int main()
{
   int n,m,k,cnt=0;
   cin>>n>>m;    
   for(int i=1;i<=n;i++){
       cin>>k;
       //以数字作为下标进行统计
       a[k]++;
   }
   //从小到大开始枚举
   for(int i=1;i<=(1<<17);i++){
       if((i|m)!=i&&a[i]!=0){
           //肯定会进入到下个数
           a[i|m]+=a[i];
           a[i]=0;
       }
       if(a[i]==1) cnt++;
   }
   cout<<cnt<<endl;
}

mcj的代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
   int n,m,a[100005];
   int i;
   map<int,int> ma,mb;
   scanf("%d%d",&n,&m);
   for (i=0;i<n;i++)
   {
       scanf("%d",&a[i]);
       mb[a[i]]=a[i]|m;
       ma[mb[a[i]]]++;
   }
   int ans=0;
   for (i=0;i<n;i++)
   {
       if (ma[mb[a[i]]]==1)
           ans++;
   }
   printf("%d\n",ans);
}

3.6198: Alice与进制转换进阶版

非常抱歉这个题目出现了问题,影响了ydqdsg非常抱歉
这个就是大数的一个题目,我们可以用大数进行模拟,当然下面的代码过不了终极版,你可以修改尝试下AC6222终极版

#include <bits/stdc++.h>
using namespace std;
//最大为16进制转2进制,一位变四位
const int N = 40005;
string c = "0123456789ABCDEF";
int ans[N];
int main()
{
   ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
   string s;
   int r1, r2;
   while (cin >> s >> r1 >> r2)
   {
       ans[0] = 0;
       int tot = 0;
       for (int i = 0, d; s[i]; i++)
       {
           if (s[i] == '-')
           {
               cout << "-";
               continue;
           }
           //s[i]对应为相应的数字
           if (s[i] >= '0' && s[i] <= '9')
               d = s[i] - '0';
           else
               d = s[i] - 'A' + 10;
           //ans是倒的,多了一位d,可能要进位,因为r1和r2的大小无法确定
           for (int j = 0; j <= tot; j++)
           {
               //把ans[j]按照r1转换,因为多了1位,要再乘一次r1
               d += ans[j] * r1;
               //获取最新的ans[j]
               ans[j] = d % r2;
               //舍去当前位
               d /= r2;
           }
           //d要新开才能存储下
           while (d)
           {
               //高位会增加
               ans[++tot] = d % r2;
               d /= r2;
           }
       }
       for (int i = tot; i >= 0; i--)
           cout << c[ans[i]];
       cout << "\n";
   }
}

Java写起来很容易

import java.io.*;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.InputStream;

public class Main {

   public static void main(String args[]) {
       Scanner sc = new Scanner(System.in);
       while(sc.hasNext()) {
           String s = sc.next();
           int r1 = sc.nextInt();
           int r2 = sc.nextInt();
           String a = new BigInteger(s,r1).toString(r2);
           System.out.println(a.toUpperCase());
       }
   }

}

4.6194: jump jump jump

这个题目可以广搜解答,广搜可以保证每次搜到的都是最近的,且每个点只会被访问一次。

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int N = 1e5 + 5;
vector<int> V[N];
int ans[N];
void bfs(int n)
{
   queue<int> Q;
   Q.push(n);
   ans[n]=1;
   while (!Q.empty())
   {
       int t = Q.front();
       Q.pop();
       for (auto X : V[t])
       {
              //如果当前点可以被更新,即现在不是最小
           if (ans[X] > ans[t] + 1)
           {
               ans[X] = ans[t] + 1;
               Q.push(X);
           }
       }
   }
}
int main()
{
   memset(ans, INF, sizeof(ans));
   int n, k;
   scanf("%d%d", &n, &k);
   for (int i = 1, x; i <= n; i++)
   {
       scanf("%d", &x);
       //没有到,建立一个边,代表一步可以从x+i跳回i
       if (x + i <= n)
           V[x + i].push_back(i);
   }
   bfs(n);
   int res = INF;
   for (int i = 1; i <= k; i++)
       res = min(res, ans[i]);
   if (res == INF)
       printf("-1\n");
   else
       printf("%d\n", res);
   return 0;
}

当然也可以记忆化搜索,这样用栈比较多,OJ的栈空间在这个题目够用

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
const int INF=0x3f3f3f3f;
int a[N],f[N];
int n,k;
int dfs(int u) {
   //跳过了n或者当前跳0步,会死循环
   if(u>n||a[u]==0) return INF;
   //已经有答案了直接返回,就是在这里记忆化的
   if(f[u]!=INF) return f[u];
   return f[u]=dfs(u+a[u])+1;
}
int main() {
   //freopen("in.txt","r",stdin);
   scanf("%d%d",&n,&k);
   for(int i=1;i<=n;i++) {
       scanf("%d",&a[i]);
   }
   memset(f,INF,sizeof f);
   f[n]=0;
   int ans=INF;
   //对于前k个分别进行搜索
   for(int i=1;i<=k;i++) {
       ans=min(ans,dfs(i)+1);
   }
   printf("%d\n",ans==INF?-1:ans);
   return 0;
}

当然也可以dp解答,因为每个点只访问一次,而且最小
dp[i]代表i~n的最小步数

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int N=1e5+5;
int a[N],b[N];
int main()
{
   int n,m,k;
   cin>>n>>m;    
   for(int i=1;i<=n;i++) cin>>a[i];
   memset(b,INF,sizeof(b));
   b[n]=1;
   for(int i=n;i>=1;i--){
       //可以到,需要更新答案
       if(i+a[i]<=n) b[i]=min(b[i+a[i]]+1,b[i]);
   }
   int minn=INF;
   for(int i=1;i<=m;i++) minn=min(minn,b[i]);
   if(minn>100000) cout<<"-1\n";
   else cout<<minn<<endl;
   
}

5.6220: Alice与函数图像

这个题目略微困难,y= - x3 - bx和 y = x3 + bx是等价的,因为他们的函数图像是对称的,x13 + bx1 - x23 + bx,有立方差公式(a-b)(a2+ab+b2)=a3-b3,以上进行合并为 ( X1 - X2 ) * ( X1 * X1 + X1 * X2 + X2 * X2 + b)
update:感谢liqiyao0430hack了标程,时间仓促,出题人没有考虑到(写的不等式错了)。
1.后面部分为1,假设(X1-X2)为素数P,后面为1,X1=P+X2
代入得到3X2 * X2+3PX2 +P*P+b为二次函数,开口向上对称轴为-2/P,最低点为(-P/2,P2/4+b)
P=2且b=0,最小值为1,X1=1,X2=-1,所以这个需要特判掉。
2.前面部分为1,X1-X2=1代入可得
是对函数3 * i * i + 3 * i = p +1 -b存在解,当然也可以直接二分,也可以判断根。判断根会超过ll,需要unsiged,当然你也可以给他进行因式分解为3i * (i+1) == p+1-b,这个不会爆ll,(p-1-c)%3 = = 0 && int(sqrt((p-1-c)/3)) * (int(sqrt(p-1-c)/3))+1)==(p-1-c)/3

二分代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int c;
bool la(LL x)
{
   //后面部分是二次的,所以要1e9
   LL l=1,r=1e9+5;
   while(l<=r)
   {
       LL mi=(l+r)/2;
       LL y=mi-1;
       //存在值x
       if(mi*mi+y*y+mi*y+c==x)
       {
           return 1;
       }
       //递增函数,小于在右边
       else if(mi*mi+y*y+mi*y+c<x)
           l=mi+1;
       else r=mi-1;
   }
   return 0;
}
int main()
{
   LL n;
   while(~scanf("%d%lld",&c,&n)){
       //特殊数据特判
       if(c==0&&n==2){
           printf("Existent\n");
           continue;
       }
       printf("%s\n",la(n)?"Existent":"Non-existent");
   }
   return 0;
}

判根的代码。由于sqrt在C++11以前是不精确的,而且unsinged会出问题,所以关闭了G++和C++的提交。

#include<bits/stdc++.h>
using namespace std;

#define LL unsigned long long
int main(){
   LL p,b;
   while(cin>>b>>p){
       if(b==0&&p==2){
           printf("Existent\n");
           continue;
       }
       //delta大于0才有解
       if(12*p-12*b-3>=0){
           LL sqr=sqrt(12*p-12*b-3);
           //必须解为整数,即能被整除
           if(sqr*sqr==12*p-12*b-3&&(3+sqr)%6==0)cout<<"Existent\n";
           else cout<<"Non-existent\n";
       }
       else cout<<"Non-existent\n";
   }
   return 0;
}

剩下的到博客,这里太长发不下 https://www.cnblogs.com/BobHuang/p/12610795.html


为解题报告打分
暂时不评分

★★
★★★
★★★★
★★★★★
发表您的评论(若贴AC代码或发表禁止言论等违禁行为将被删除并扣除积分)

|返回 |   | 转到页头|
Copyright @ 2008-2024(浙ICP备2022001332号), TZOJ. All Rights Reserved.