NOIP 2017 选讲
- 小凯的疑惑
数论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都可）
分析一下这道题目
奶酪大概是介个样子！
技巧：如何判断两个球体之间的距离？
#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总的代码超级赞 时间复杂度
