python解acm题_2020年常熟理工学院第一届线上ACM选拔赛题解(Python版)

这个题目是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^,100^6^= 10^12^=1e12

考虑所有的斜线，就是已知100以内互质对数 * n^2^

100以内互质对数为6087，实际可能的是1547（优化过的）

1547 * n * n = 1e7，当然还有常数，但是足够通过这个题目了

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

python实在太慢了，这个代码本地跑一个大样例要7s

import math

n = int(input())

s = [''] * n

for i in range(n):

s[i]=input()

vis=[[False] * n for i in range(n)]

V=[]

def cal(cnt):

if(cnt>=3):

return cnt * (cnt - 1) * (cnt - 2) // 6

return 0

def add(i,j,ai,aj):

cnt = 0

while j < n and i < n:

vis[i][j] = True

if s[i][j] != '.':

cnt = cnt+1

i = i + ai

j = j + aj

return cal(cnt)

def sub(i,j,ai,aj):

cnt = 0

while j >= 0 and i < n:

vis[i][j] = False

if s[i][j] != '.':

cnt = cnt+1

i = i + ai

j = j - aj

return cal(cnt)

for i in range(1,n+1):

for j in range(1,n+1):

if math.gcd(i, j) == 1 and min(n / i, n/ j) > 2 :

V.append([i, j])

ans = 0

for X in V:

for i in range(n):

for j in range(n):

if vis[i][j]==False:

ans = ans + add(i, j, X[0], X[1])

for i in range(n):

for j in range(n):

if vis[i][j]==True:

ans = ans + sub(i, j, X[0], X[1])

for j in range(n):

ans = ans + add(0, j, 1, 0)

for i in range(n):

ans = ans + add(i, 0, 0, 1)

print(ans)

这个是位运算的题目，这是“按位或”运算符，||是逻辑或，两个相应的二进制位中只要有一个为1，该位的结果值为1，即有1得1。曾经写过一个operator的理解，有兴趣可以看看。

我们可以以当前数字作为下标进行统计个数。或会让这个数字变大(有些位上多1)，所以我们从小的数字开始枚举，如果或的值不为i，说明异或的新值可以多a[i]个，当前清空，如果这个数字恰巧只有一个，那只能当读出现了，统计下来。

update: 要么a[i]不或m，要么或m，如果存在显然或m，这样会减少。一个数字或上两次并不会变得更大，所以一次处理也可以。

100000 并不是一个规整的数，我们可能或为2倍(其实就是1<<17=131072,略大于是最省的)，也就是你要找到大于他的二进制数

n,m=map(int,input().split())

b=map(int,input().split())

a=[0]*(1<<17)

for i in b:

a[i] = a[i] + 1

ans=0

for i in range(1<<17):

if (i|m)!=i and a[i]!=0 and (i|m)<(1<<17):

a[i|m] = a[i|m] + a[i]

a[i] = 0

if a[i]==1:

ans = ans + 1

print(ans)

非常抱歉这个题目出现了问题，影响了ydqdsg非常抱歉

py的int很大很大，我们可以直接使用，但是他没有很方便的函数，转到r2进制需要手写

你可以看看cpp的实现修改代码尝试下AC6222终极版

def dec_to_base_r(num,r):

if num<0:

return "-"+dec_to_base_r(-num,r)

base = [str(x) for x in range(10)] +[chr(x) for x in range(ord('A'),ord("A")+6)]

l = []

while True:

num,rem = divmod(num,r)

l.append(base[rem])

if num == 0:

return "".join(l[::-1])

while True:

try:

n,r1,r2=map(str,input().split())

n=int(n,int(r1))

print(dec_to_base_r(n,int(r2)))

except EOFError:

break

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());

}

}

}

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

当然也可以记忆化搜索。

当然也可以dp解答，因为每个点只访问一次，而且最小

dp[i]代表i~n的最小步数。

n,k = map(int,input().split())

a = list(map(int,input().split()))

dp = [int(1e9)]*(n+1)

dp[n] = 1

for i in range(n,0,-1):

if(i+a[i-1]<=n):

dp[i]=min(dp[i+a[i-1]]+1,dp[i])

minn=int(1e9)

for i in range(k):

minn=min(minn,dp[i+1])

if(minn==int(1e9)):

print(-1)

else:

print(minn)

这个题目略微困难，y= - x³ - bx和 y = x³ + bx是等价的，因为他们的函数图像是对称的，x1³ + bx1 - x2³ + bx，有立方差公式(a-b)(a²+ab+b²)=a³-b³，以上进行合并为 ( 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，最低点为

[(-frac{P}{2} ,frac{P^2}{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

(p-1-c)%3 == 0 and int(sqrt((p-1-c)/3)) * (int(sqrt(p-1-c)/3))+1)==(p-1-c)/3

import math

while True:

try:

b,p=map(int,input().split())

f=int(math.sqrt((p-1-b)/3))

if b==0 and p==2:

print('Existent')

elif (p-1-b)%3 == 0 and f * (f+1)==(p-1-b)//3:

print('Existent')

else :

print('Non-existent')

except EOFError:

break

我们可以对24点的代码进行改造，我们可以判断是是不是有4和9然后进行变换就可以了。

当然也可以带上flag搜，dfs就是这样，暴力和好写的一个平衡。

from itertools import permutations

import math

def la(s):

if s=='A':

return 1

if s=='JOKER':

return 0

if s=='J':

return 11

if s=='Q':

return 12

if s=='K':

return 13

return int(s)

f = 0

def dfs(pos,flag,sum):

global f

if f==1:

return

if pos==3:

if sum==16:

f=1

return

if pos==0:

if a[pos]==4 or a[pos]==9 :

dfs(pos+1,0,int(math.sqrt(a[pos])))

dfs(pos+1,1,a[pos])

else:

if (a[pos]==4 or a[pos]==9) and flag==1:

dfs(pos+1,0,sum*int(math.sqrt(a[pos])))

dfs(pos+1,0,sum//int(math.sqrt(a[pos])))

dfs(pos+1,0,sum+int(math.sqrt(a[pos])))

dfs(pos+1,0,sum-int(math.sqrt(a[pos])))

dfs(pos+1,flag,sum*a[pos])

if a[pos]!=0:

dfs(pos+1,flag,sum//a[pos])

dfs(pos+1,flag,sum+a[pos])

dfs(pos+1,flag,sum-a[pos])

T=int(input())

for i in range(T):

f=0

tmp1=map(str,input().split())

tmp2=[la(i) for i in tmp1]

b = permutations(tmp2)

for a in b:

dfs(0,1,0)

if f==1:

print('YES')

else:

print('NO')

排成圈，其实就是扩展一次。所以可以边扩展边记录，找到最大值即可。

这个题目很多人被卡超时，如果使用C++请关闭输入输出同步，尽量使用scanf和printf。不要混用。如果使用JAVA你可以去codeforces看下peter的代码，把它的Java读入抄下来。

关闭同步代码：ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

这个自己也可以百度，也是考点，如果还不能通过就要考虑使用快读

def la():

n = int(input())

a = list(map(float,input().split()))

a = a+a

dp = [0]*(n+n)

dp[0] = 1

for i in range(1,n+n):

if a[i] <= a[i-1]:

dp[i] = dp[i-1]+1

else:

dp[i]=1

ans=0

for i in range(n+n):

ans=max(ans,min(dp[i],n))

print(ans)

T=int(input())

for i in range(T):

la()

这个题目可以循环判断，也可以直接搜索

n=15

def la(c):

for i in range(11):

for j in range(11):

if s[i][j]==c and s[i][j]==s[i+1][j+1] and s[i][j]==s[i+2][j+2] and s[i][j]==s[i+3][j+3] and s[i][j]==s[i+4][j+4] or s[i][n-j-1]==c and s[i][n-j-1]==s[i+1][n-j-2] and s[i][n-j-1]==s[i+2][n-j-3] and s[i][n-j-1]==s[i+3][n-j-4] and s[i][n-j-1]==s[i+4][n-j-5]:

return True

for i in range(n):

for j in range(11):

if s[i][j]==c and s[i][j]==s[i][j+1] and s[i][j]==s[i][j+2] and s[i][j]==s[i][j+3] and s[i][j]==s[i][j+4]:

return True

for i in range(11):

for j in range(n):

if s[i][j]==c and s[i][j]==s[i+1][j] and s[i][j]==s[i+2][j] and s[i][j]==s[i+3][j] and s[i][j]==s[i+4][j]:

return True

return False

while True:

try:

s = [''] * 15

for i in range(15):

s[i]=input()

if la('X'):

print("Bob Wins!")

elif(la('O')):

print("Alice Wins!")

else:

print("continue")

except EOFError:

break

这个就是方程的判断，y=ax+b，斜率为无穷对应无数个解，如果a=0，且y!=b是无解

while True:

try:

y,a,b=map(int,input().split())

if a==0 :

if y==b :

print("Infinite")

else :

print("Unsolvable")

else :

print('%.2f' %((y-b)/a))

except EOFError:

break

python可以直接除，默认就是得到小数

while True:

try:

a,b,c,d=map(int,input().split())

if a/b > c/d:

print(a,'/',b,'>',c,'/',d)

elif a/b < c/d:

print(a,'/',b,'<',c,'/',d)

else:

print(a,'/',b,'=',c,'/',d)

except EOFError:

break

可以直接勾股定理，也可以相似(两小三角形相似，另一直角边为(b*a/c))，而且怎么AC都能对。勾股数恰好满足可以凑答案，甚至正好整除。

这个题错误的是因为多组数据。

while True:

try:

a,b,c=map(int,input().split())

print('%.3f' %(a*a*b*1.0/2/c))

except EOFError:

break

最后

以上就是谦让鸡翅为你收集整理的python解acm题_2020年常熟理工学院第一届线上ACM选拔赛题解(Python版)的全部内容，希望文章能够帮你解决python解acm题_2020年常熟理工学院第一届线上ACM选拔赛题解(Python版)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。