|
| ||
|
|
|
|
2020年常熟理工学院第一届线上ACM选拔赛
|
本次题目难度顺序基本从难到易，在这里非常感谢出题组同学的真情付出。此博客原文地址:https://www.cnblogs.com/BobHuang/p/12610795.html
这个题目是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;
}
这个是位运算的题目，这是“按位或”运算符，||是逻辑或，两个相应的二进制位中只要有一个为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);
}
非常抱歉这个题目出现了问题，影响了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());
}
}
}
这个题目可以广搜解答，广搜可以保证每次搜到的都是最近的，且每个点只会被访问一次。
#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;
}
这个题目略微困难，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
