AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

9.12讲义

作者: 作者的头像   robot_1 ,  2019-09-12 14:54:37 ,  所有人可见 ,  阅读 1123


7


3

NOIP 2017 选讲

  1. 小凯的疑惑
    数论exgcd

先来一道简单开开胃
也顺便 说一下 gcd 和lcm 和本题没有什么特别大的关系
数学好的同学可以用裴蜀定理
而像我这种蒟蒻可以打暴力或者直接找规律qaq

//baoli
#include<iostream>
#include<cmath>
using namespace std;
int flag[1000010];
int maxx;
int main()
{
    int a,b,x,y;
    cin>>a>>b;
    for(x=0;x<=1000;x++)
      for(y=0;y<=1000;y++)
        flag[a*x+b*y]=1;
        for(int i=1000;i>=0;i--)
        {
            if(flag[i]==0)     maxx=max(i,maxx);

          }
          cout<<maxx;
    return 0;

}
//gcd(a,b)=1;
/*
3 7
1,2,4,5,8,11,
3*4=12
3+7+3=13
7*2
*/
#include<iostream>

using namespace std;
int main()
{
    long long  a,b;
    cin>>a>>b;
    cout<<a*b-a-b;
    return 0;
}
/*  我在这里找的规律
3 4 5  6  (3-1)*(4-1)
3 5 7  8  (3-1)*(5-1)
3 7 11  12  (3-1)*(7-1)

(a-1)(b-1)==ab-a-b
*

证明
定理: 对于正整数p , q满足gcd(p, q) = 1, 我们有px + qy = n 无非负整数解的最大正整数n 为pq - p - q . 证明如下:

我们首先利用反证法, 证明px + qy ≠ pq - p - q : 我们假设存在正整数x 和y 使得px + qy = pq - p - q , 则有

px + qy = pq - p - q

p(x + 1) + q(y + 1) = pq

∵g gcd(p, q) = 1,p | q(y + 1)∵gcd(p,q)=1,p∣q(y+1)

∴p p | y + 1∴p∣y+1

同理,q | x + 1

接着我们令y + 1 = pj , x + 1 = qk . 则有
pqk + qpj = pq
pq(j + k) = pq
注意到x, y≥ 0 , 我们有y+1≥1 且x+1≥1 , 因而j≥1 且k≥1 . 因而j+k≥2 , 因而假设不成立.
————————————————
参考 dalao

2.奶酪(并查集 bfs dfs都可)
分析一下这道题目

61d8243ft71cf7a246125&690.gif
奶酪大概是介个样子!
技巧:如何判断两个球体之间的距离?
123.png

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
ll dis(ll x,ll y,ll z,ll x1,ll y1,ll z1)
{
    return (x-x1)*(x-x1)+(y-y1)*(y-y1)+(z-z1)*(z-z1);
}
int f[10000];
int find(int x)
{
    return f[x]==x?x:f[x]=find(f[x]);
}
ll r;
int n,h,T;
ll x[100000],y[100000],z[100000];
int d1[100000],d2[100000];
//f1记录与顶面相交的洞的序号
//f2记录与底面相交的洞的序号
int ding,di;
int main()
{
    cin>>T;
    while(T--)
    {
        cin>>n>>h>>r;
        int ding=0,di=0;
        for(int i=1;i<=n;i++)
          f[i]=i;
          for(int j=1;j<=n;j++)
            { cin>>x[j]>>y[j]>>z[j];
              if(z[j]+r>=h)  
             {
                ding++;
                 d1[ding]=j;
             }
             if(z[j]-r<=0)  
             {
                di++;d2[di]=j;
            }
              for(int k=1;k<=j;k++)
             {
                if ((x[j]-x[k])*(x[j]-x[k])+(y[j]-y[k])*(y[j]-y[k])>4*r*r) continue;
                if (dis(x[j],y[j],z[j],x[k],y[k],z[k])<=4*r*r){
                    int a1=find(j);
                    int a2=find(k);
                    if (a1!=a2) f[a1]=a2;
             }
     } 
            }

            int ans=0;
            for(int i=1;i<=ding;i++){
              for(int j=1;j<=di;j++)
              {
                  if(find(d1[i])==find(d2[j]))
                {  
                  ans=1;
                  break;
                }
              }
              if(ans==1) break;
            }
              if(ans==1) cout<<"Yes"<<endl;
              else cout<<"No"<<endl;
    }
    return 0;
}

3时间复杂度 (毒瘤题)

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
char s[13];
int getfz()//返回题目给的复杂度
{
    cin>>s;//把O()一起读进来
    if(s[2]=='1')return 0;//常数复杂度O(1)
    int len=strlen(s);
    if(len==6)return s[4]-'0';//O(n^w)长度为6,所以w是一位数
    return (s[4]-'0')*10+(s[5]-'0');
}
int getx()//x和y格式一样,可以用同一个函数
{
    cin>>s;//先读进来
    if(s[0]=='n')return 100;//把n当做100
    int len=strlen(s);
    if(len==1)return (s[0]-'0');//长度为1,所以是一位数
    return (s[0]-'0')*10+(s[1]-'0');
}
bool used[233];//标记变量名是否被用过
char stac[101];//变量名栈
bool loc[101];//是否锁上了
bool add[101];//是否加复杂度了
int main()
{
    //freopen("a.in","r",stdin);
    int t;
    cin>>t;
    while(t--)
    {
        memset(used,0,sizeof(sf));
        memset(stac,0,sizeof(stac));
        memset(loc,0,sizeof(loc));
        memset(add,0,sizeof(add));
        //先都清个零
        int l;
        cin>>l;
        int fz=getfz();
        int tos=0,lock=0;//tos:栈顶 lock:锁定层数
        int mac=0,now=0;//mac:最大复杂度 now:当前复杂度
        int err=0,F=0;//err:错误 F:F比E多的个数
        while(l--)
        {
            char opt;
            cin>>opt;
            if(opt=='F')
            {
                F++;
                //处理i
                char i;
                cin>>i;
                if(used[i])err++;//变量名重复
                used[i]=1;
                stac[++tos]=i;
                //处理x,y
                int x=getx(),y=getx();
                if(x>y){loc[tos]=1;lock++;}//进不去,上锁
                if(lock)continue;//有锁就不能加复杂度
                if(l<100&&r==100){add[tos]=1;now++;}
                mac=max(mac,now);
            }
            else
            {
                F--;
                if(F<0)err++;//E比F多,语法错误
                if(loc[tos]){lock--;loc[tos]=0;}//有锁拆锁
                if(add[tos]){now--;add[tos]=0;}//加了减掉
                used[stac[tos]]=0;//释放变量名
                tos--;
                if(tos<0)tos=0;//防止访问负坐标
            }
        }
        if(F!=0)err++;//F和E不匹配,语法错误
        if(err){cout<<"ERR"<<endl;continue;}
        if(mac==fz){cout<<"Yes"<<endl;}
        else cout<<"No"<<endl;
    }
    return 0;
}

y总曾经说过,做模拟题 重要的步骤是将模块化
这个题目A的意思
是 for(int i=x;i<=y;i
) 一开始我看反了
通过我们对c++的学习 for循环时如何出现语法错误呢
如果 x>y 这样就会GG掉
通过常识 我们也可以计算时间复杂度
循环复杂度的判定
1.循环出错,忽略其他循环,直接输出答案ERR。
2.该循环不执行,不论与之嵌套的循环复杂度是多少,均返回常数复杂度,。
把n变成一个常数,这样对比大小的时候就不用写一堆if了。
详细的我会在课上说。
y总的代码超级赞 时间复杂度

6 评论


用户头像
yxc   2019-09-12 22:42         踩      回复

不错,加油!

用户头像
robot_1   2019-09-13 20:54         踩      回复

谢谢y总!


用户头像
ytczy666   2019-09-12 21:09         踩      回复

真牛
tb神仙

用户头像
robot_1   2019-09-13 20:54         踩      回复

谢谢!


用户头像
秦淮岸灯火阑珊   2019-09-12 17:37         踩      回复

棒棒哒!

用户头像
robot_1   2019-09-13 20:54         踩      回复

谢谢!


App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息