目录
数学问题模拟
计算多边形面积(叉乘)
解题思路：叉乘的运用
原理是在平面上取(0,0)来分割多边形为多个三角形，然后用叉乘来求三角形的面积（有向）再求和。这样的话可以把凸N多边形转化为N个三角形，然后求解N个三角形即可，输入顶点的顺序 无论是顺时针还是逆时针均可。
题目要求：计算多边形面积
方法：把n多边形分割成n-2个三角形，分别求和，然后相加
注意：分割的所有三角形有一个公共的顶点，这里选择0点位公共点
注：题中给出的点的顺序为逆时
叉乘的性质：设两向量P和Q
1.P ×Q > 0 则Q在P的逆时针方向
2.P ×Q < 0 则Q在P的顺时针方向
3.P ×Q = 0 则Q和P共线，方向可能相同也可能不相同
叉乘法：已知三角形三点坐标为(x1,y1) (x2,y2) (x3,y3)
则三角形面积为=(1/2)*[(x2y3-x3y2)-(x1y3-x3y1)+(x1y2-x2y1)]
参考资料：计算几何基础
之所以不用海伦公式：有一个三角形，边长分别为a、b、c，三角形的面积S可由以下公式求得：S=√[p(p-a)(p-b)(p-c)] 而公式里的p为半周长： p=(a+b+c)/2
是由于1：计算量大。2：精度损失
#include<stdio.h>
#include<stdlib.h>
typedef struct point
{
int x,y;
}point;
point a[110];//n的范围限制
double area(point p,point q)
{
return p.x*q.y-q.x*p.y;//叉乘计算面积的公式，简化的，是以(0,0)为起始点划分的
/*叉乘法：已知三角形三点坐标为(x1,y1) (x2,y2) (x3,y3) 则三角形面积为=(1/2)*[(x2y3-x3y2)-(x1y3-x3y1)+(x1y2-x2y1)]*/
}
int main()
{
int i,n;
double sum;
while(~scanf("%d",&n)&&n)
{
for(i=0;i<n;i++)
scanf("%d%d",&a[i].x,&a[i].y);
sum=area(a[n-1],a[0]);//其实a[n-1],a[0]是一个点，即初始值sum==0
for(i=1;i<n;i++)
sum+=area(a[i-1],a[i]);//这点注意最后i==n-1 ；（求面积有一个坐标是（0，0，0））
printf("%.1lf\n",0.5*sum);
}
system("pause");
return 0;
}
C++中sin函数的用法
用的是弧度，用的是弧度，用的是弧度
那么角度转换为弧度的方法为
#define PI 3.1415927
#define Pi acos(-1)
x=(ct/180*PI);
x为弧度，ct为角度
同理，cos，tan，asin，atan，acos都是用的弧度哦
计算圆内接多边形边长
先求一条边的边长。如图，n边形对应的 θ=2n2π=nπ，边长就是 sinθ=2rsinnπ。 再求i到j最短经过几条边： l=(i−j)modn 最后答案就是 sinnπ⋅(i−j)modn
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+7;
#define Pi 3.1415926535
int main()
{
ll n,r,i,j;
cin>>n>>r>>i>>j;
if(i>j)swap(i,j);
double angel=180/n;
double ans=(2*r)*sin(angel/180*Pi);
double t=min(n-j+i,j-i);
ans*=t;
printf("%.9lf\n",ans);
}
1.强迫症的lpl
例题1：强迫症的lpl
lpl拥有nnn个游戏，每个游戏的名字长度不同，但是lpl有强迫症，他很看不惯这些长度不一样的名字，所以他打算把名字修改为相同的长度，但是他的电脑出了故障，他每次只能将其中的n−1n-1n−1个名字加一个字，问他最少经过多少次操作就能让全部的名字长度相同。
思路：用cin会超时。。
#include<iostream>
#include<sstream>
#include<cstdio>
using namespace std;
typedef long long ll;
const int maxn=1000005;
int t,n,m,a[maxn],minn;
int main()
{
scanf("%d",&t);
while(t--)
{
minn=233333333;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
minn=min(minn,a[i]);
}
ll ans=0;
for(int i=0;i<n;i++)
ans+=a[i]-minn;
cout<<ans<<endl;
}
return 0;
}
2.喜欢斐波那契数的冰冰酱（斐波那契，同余定理）
例题2： 喜欢斐波那契数的冰冰酱
ACM的冰冰酱是一位普通（并不）的女大学生，她最喜欢的就是斐波拉契数了，斐波那契数列是一个从第3项开始，每一项都等于前两项之和的神奇数列。 冰冰酱每天都会想到许多与斐波那契数列有关的问题，有一天冰冰酱忽然想知道斐波那契数列中的任意两个位置aaa到bbb的全部斐波那契数的和是奇数还是偶数呢，那么你可以帮助冰冰小姐姐解决这个问题嘛。
思路：斐波那契数列第一项第二项为奇数，第三项为偶数，三个一循环，找规律即可。注意题目中数可以达到10的100次方，所以知道一个结论很重要：例如23685%3=0，2+3+6+8+5=24%3=0；
同余定理：
优先级 * 高于 %
所以有如下代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+10;
int t,c,d;
string a,b;
int get(string s)
{
int len=s.length();
int sum=0;
for(int i=0;i<len;i++)
sum+=s[i]-'0';
return sum;
}
int main()
{
cin>>t;
while(t--)
{
cin>>a>>b;
c=get(a)%3;
d=get(b)%3;
if((c==1&&d==1)||(c==0&&d==1)||(c==2&&d==2)||(c==2&&d==0))cout<<1<<endl;
else cout<<0<<endl;
}
return 0;
}
3.喜欢膜法的菜菜K（__gcb()，辗转相减）
例题3：
喜欢膜法的菜菜K
在ACM集训队群中，最喜欢膜法的就是菜菜K了，以至于他终于发现了一个神奇的膜法规则，但是同时他也发现了一个难题。 在这个群中，每个人都有一个地位值，菜菜K发现，只要A膜B，那么A的地位值就会变成A的地位减去B的地位（注意地位值一定为正整数，即一个人只能膜比他地位低的人），菜菜K想知道，所有人能得到的最低地位是多少？
思路：求这一组数的最大公约数就行了（类似辗转相减法）
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+10;
int t,n,a,ans;
int main()
{
cin>>t;
while(t--)
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a;
if(i==1)ans=a;
else ans=__gcd(ans,a);//__gcd函数，直接求最大公约数；
}
cout<<ans<<endl;
}
return 0;
}
3.5最大公约数的应用：
黑板上有3个不同的初始数字，每一次可以选择黑板上的任意2个不同的数字，然后计算这两个数字之间差的绝对值，如果这个绝对值不再黑板上，就把他写到黑板上。问最多能添加多少个数字
黑板上的数
#include<bits/stdc++.h>
using namespace std;
long long gcd(long long a,long long b)
{
return b==0?a:gcd(b,a%b);
}
int main()
{
int n;
scanf("%d",&n);
for(int i=0; i<n; i++)
{
long long x,y,z;
scanf("%lld%lld%lld",&x,&y,&z);
long long num=gcd(gcd(x,y),z);
long long result=((max(max(x,y),z))/num)-3;
printf("%lld\n",result);
}
return 0;
}
4.菜菜k的序列(选3个数使和为0,数据较大)
菜菜k的序列(1)
题目描述
菜菜k最近很无聊，于是他研究起了序列。现在他有一个序列，他想从序列里选出三个数使它们的和为0，菜菜k想问你一共有多少种选法。
t组数据
第一行为t，代表t组数据,t<= 100
每组数据中：
第一行：序列长度n（3<=n<=1,000）
第二行：n个以空格隔开的数 a1,a2...ai...an
, (−200,000<=ai<=200,000)
思路：用数组做即可
#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
int t,a[maxn],n,ans,sum[5000000],temp;//数组应该开大一些题中a是2e5要注意数据否则容易RE
int main()
{
cin>>t;
while(t--)
{
cin>>n;
ans=0;
memset(a,0,sizeof(a));
memset(sum,0,sizeof(sum));
for(int i=0;i<n;i++)
cin>>a[i];
sum[500000+a[0]]++;
for(int i=1;i<n;i++)//i=0时做无用功；必须三个数相加
{
for(int j=i+1;j<n;j++)
{
temp=a[i]+a[j];//先算两数之和;
ans+=sum[500000-temp];//再求相反数即可;
}
sum[500000+a[i]]++;//三个数加一块，不能算上自己，所以要在自己遍历完之后再++
}
cout<<ans<<endl;
}
return 0;
}
5.做计数(完全平方数,因数,满足等式)
两边平方，得 i+j+2ij=k
显然仅当 i j都是整数且 i j 为完全平方数时才会对应一个符合条件的 k。
枚举 [1,n]] 中所有的完全平方数（完全平方数可以表示为 x2 ，只需要枚举 x ，再枚举这个完全平方数的因数，统计答案。
O(n)枚举完全平方数 O(n),枚举因数，时间复杂度 O(n) ，可以进一步优化。
第一个for枚举1-n的完全平方数i*i，第二个for枚举i*i的因数
就是i*i实际上是i*j，每一个完全平方数+1种，只要这个完全平方数有因数，那么i j和j i各是一种情况所以要+2。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+7;
const ll mod=1e9+7;
ll n,ans;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i*i<=n;++i)
{
for(int j=1;j<i;++j)
if(i*i%j==0)ans+=2;
ans++;
}
cout<<ans<<endl;
return 0;
}
7.M-破碎的愿望
M-破碎的愿望
广工的腾讯杯，是真的大佬，一套题附赠一篇小说
题目描述
「Rhongomyniad!」 圣枪击穿了圣杯，原本就仅有一个碎片的虚假圣杯，现在更是变成了一撮辉煌的粉末，散失地飞舞在空中。是破碎的无数梦想的实体。并不是为了什么正义，仅仅是有必要结束这一切。由曾是御主(master)的我取得的圣杯的碎片，应当由我去结束这一切。 「师父」 「回去了，格蕾」身边的黑泥应该不久就会自行消散，回归大源了吧 「为什么会变成这样，圣杯不是万能的愿望机吗」 「因为无法实现的愿望就是无法实现啊」我叹了一口气「世界的前进只是在不断的循环。那个人固然是天才，但无法做到的事情就是无法做到。所以他放弃了」 「我不明白」 「人类史的最初可以比作一个字符串，把原本的字符串翻转后拼接到原来的字符串后面，就会得到一个新的字符串，如此的反复，人类史就是如此进行着无限的延伸。所以如果你想要知道这个无限延伸的字符串上的某个字符，是很简单的一件事。但不可能得到那些不存在于这个字符串上的字符啊。」 「那师父为什么你还不放弃呢」 「我想证明这是错误的」 格蕾没有再多问 。
输入描述:
第一行输入n (1<=n<=30)和k (1<=k<=1018)，代表字符串最初的长度和所需要知道的字符的序号第二行输入一个仅由小写字符组成的字符串str，(|str|==n)。其中|str|代表字符串的长度。
输出描述:
输出第k个字符
题确实不难，有点巧妙。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
string s,temp;
ll n,k;
int main()
{
cin>>n>>k;
k--;
cin>>s;
temp=s;
reverse(temp.begin(),temp.end());
s+=temp;
k=k%(2*n);
cout<<s[k]<<endl;
return 0;
}
P1158 导弹拦截(前缀后缀优化, 求最短距离)
P1158 导弹拦截
题目描述
经过 11年的韬光养晦，某国研发出了一种新的导弹拦截系统，凡是与它的距离不超过其工作半径的导弹都能够被它成功拦截。当工作半径为 0时，则能够拦截与它位置恰好相同的导弹。但该导弹拦截系统也存在这样的缺陷：每套系统每天只能设定一次工作半径。而当天的使用代价，就是所有系统工作半径的平方和。
某天，雷达捕捉到敌国的导弹来袭。由于该系统尚处于试验阶段，所以只有两套系统投入工作。如果现在的要求是拦截所有的导弹，请计算这一天的最小使用代价。
思路：
这道题首先要明确所有导弹不是被1号系统拦截就是被2号系统拦截
我们看到这道题的数据范围是10的5次方，大概是nlogn复杂度，联想到sort排序
让我们思考一下最优解，在最优解中1号系统肯定先拦下距离自己近的
如果1号去拦距离它远的导弹的话，其实就捎带脚的把近的导弹拦截了
如果我们把所有导弹按照对1号的距离进行升序排序，通过刚才的思考我们知道肯定是1号拦截一个前缀，剩下的后缀交给2号
那么我们枚举一下这个前缀和后缀的分界点即可（分界点我们此处定义为前缀的最后一个点）
前缀处理的1号系统代价比较好算，就是分界点到1号系统的距离
2号系统此时就不能再排序看后缀谁是最大的来计算代价，此时需要我们预处理出来一个数组，让d[i]=包括第i以及它后面的导弹中最远距离（转）
#include<bits/stdc++.h>
#define debug cout<<"ok"<<endl
typedef long long ll;
using namespace std;
const int maxn= 2e5+5;
const int mod = 1e9+7;
int x1,x2,y_1,y2,n,dis[maxn],ans;
struct node
{
int x,y;
}a[maxn];
bool cmp(node b,node c)
{
int p=(x1-b.x)*(x1-b.x)+(y_1-b.y)*(y_1-b.y);
int q=(x1-c.x)*(x1-c.x)+(y_1-c.y)*(y_1-c.y);
return p<q;
}
int main()
{
ans=0;
cin>>x1>>y_1>>x2>>y2;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i].x>>a[i].y;
sort(a+1,a+1+n,cmp);
for(int i=n;i>=1;i--)
{
int tmp=(x2-a[i].x)*(x2-a[i].x)+(y2-a[i].y)*(y2-a[i].y);
dis[i]=max(dis[i+1],tmp);
}
ans=dis[1];
for(int i=1;i<=n;i++)
{
int tp=(x1-a[i].x)*(x1-a[i].x)+(y_1-a[i].y)*(y_1-a[i].y);
tp+=dis[i+1];//由于d[i]所保留的最大值包括i，而此时i属于前缀
ans=min(tp,ans);
}
ans=min(ans,dis[1]);
cout<<ans<<endl;
return 0;
}
1.CF11B Jumping Jack(跳,每次距离+1,跳到一个坐标点上)
CF11B Jumping Jack
题意翻译
杰克最近正在练习他的弹跳技术。目前，他位于数轴的零点，他想到达点x。为了训练，他决定第一次跳一个单位，然后每跳一次都比前一次长。他每一次跳跃都可以向左或向右，他想知道他最少需要跳多少次才能到达点x。
输入格式
输入只有一行，一个整数x (-109<=x<= 109)。
输出格式
输出要到达x的最少跳跃次数。
题意是求到达x的最少跳跃次数。首先由于对称，x与是-x是等效的，因此均把负数看做正数。设最少跳跃次数为n，那么可以得到一个结果 d=(±1)+(±2)+...+(±n)d=(±1)+(±2)+...+(±n)。
最快的跳法是往一个方向一直跳。如果恰好能到x，这样肯定是跳跃次数最小。如果不能恰好跳到，那么我们设y为以这种跳法得到的第一个比x大的点，如果y-x为偶数，可以将第(y-x)/2步往左跳，这样就能恰好跳到x了；如果y-x为奇数，那么继续跳直到与x的差为偶数即可。
#include<bits/stdc++.h>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stdio.h>
#include<cmath>
#define debug cout<<"ok"<<endl
typedef long long ll;
const int maxn=1e4+10;
const int mod=1e9+7;
using namespace std;
inline int read()//快读
{
int f=0,x=0;
char ch=getchar();
while(ch>'9'||ch<'0'){f|=(ch=='-');ch=getchar();}
while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return f?-x:x;
}
int x,ans;
int main()
{
x=read();
x=abs(x);//因为是坐标轴，向左向右无所谓
int now=1;//让他一直向右跳，如果越界了就让之前的第（now-x）/2步往左跳（往左跳意味着now向左减少now-x的距离就是直接到达x）
if(x==0){cout<<0<<endl;return 0;}//特判
for(int i=1;!ans;++i,now+=i)//模拟往后跳
if(now==x||(now>x&&!((now-x)&1)))//一旦恰好到达x或者now与x的差值为偶数就输出
ans=i;
cout<<ans<<endl;
return 0;
}
2.CF632A Grandma Laura and Apples
CF632A Grandma Laura and Apples
题意翻译 题意:有nnn个顾客买老太太的苹果，单价ppp，每个顾客买老太太所拥有苹果的一半，老太太会对某些顾客优惠即送半个苹果，最后苹果都卖光了，求总共卖了多少钱。
half表示不送苹果，halfplus即对顾客赠送半个苹果。
#include<bits/stdc++.h>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stdio.h>
#include<cmath>
#define debug cout<<"ok"<<endl
typedef long long ll;
const int maxn=1e4+10;
const int mod=1e9+7;
using namespace std;
inline int read()
{
int f=0,x=0;
char ch=getchar();
while(ch>'9'||ch<'0'){f|=(ch=='-');ch=getchar();}
while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return f?-x:x;
}
ll n,p,sum,a;//数据太大注意开 long long;
string s[maxn];
int main()
{
n=read();p=read();
for(int i=1;i<=n;i++)cin>>s[i];
for(int i=n;i>=1;i--)
{
a*=2;
if(s[i]=="halfplus")a+=1;
sum+=a;//每一次的a中有一半是自己新买的（送半个的话另外半个是自己花钱买的）
}
cout<<sum*p/2<<endl;//sum中有一半是花钱买的，所以sum*（p/2）乘单价的一半
return 0;
}
3.无线网络覆盖
题目描述
随着智能手机的日益普及，人们对无线网的需求日益增大。某城市决定对城市内的公共场所覆盖无线网。假设该城市的布局为由严格平行的 129条东西向街道和
129 条南北向街道所形成的网格状，并且相邻的平行街道之间的距离都是恒定值
1。东西向街道从北到南依次编号为 0,1,2…128，南北向街道从西到东依次编号为 0,1,2…128。东西向街道和南北向街道相交形成路口，规定编号为 x 的南北向街道和编号为 y 的东西向街道形成的路口的坐标是 (x,y)。在某些路口存在一定数量的公共场所。由于政府财政问题，只能安装一个大型无线网络发射器。该无线网络发射器的传播范围是一个以该点为中心，边长为 2d 的正方形。传播范围包括正方形边界。现在政府有关部门准备安装一个传播参数为 d 的无线网络发射器，希望你帮助他们在城市内找出合适的路口作为安装地点，使得覆盖的公共场所最多。
输入格式
第一行包含一个整数 d，表示无线网络发射器的传播距离。第二行包含一个整数 n，表示有公共场所的路口数目。接下来 n 行，每行给出三个整数 x,y,k，中间用一个空格隔开，分别代表路口的坐标 (x,y) 以及该路口公共场所的数量。同一坐标只会给出一次。
输出格式
输出一行，包含两个整数，用一个空格隔开，分别表示能覆盖最多公共场所的安装地点方案数，以及能覆盖的最多公共场所的数量。
#include<bits/stdc++.h>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stdio.h>
#include<cmath>
#include<deque>
#define debug cout<<"ok"<<endl
typedef long long ll;
const int maxn=1e3+10;
const int mod=1e9+7;
using namespace std;
int n,mp[maxn][maxn],d,x,y,num,ans=1,maxx=0;
int main()
{
cin>>d>>n;
for(int i=1;i<=n;i++)
{
cin>>x>>y;
cin>>mp[x+20][y+20];//这个输入很关键呀，快气死我了
}
for(int i=20;i<=148;i++)
{
for(int j=20;j<=148;j++)
{
for(int k=i-d;k<=i+d;k++)
for(int l=j-d;l<=j+d;l++)
num+=mp[k][l];
if(num==maxx)
ans++;
else if(maxx<num)ans=1;
maxx=max(maxx,num);
num=0;
}
}
cout<<ans<<" "<<maxx<<endl;
return 0;
}
P1981 表达式求值 scanf的妙用
题目描述
给定一个只包含加法和乘法的算术表达式，请你编程计算表达式的值。
输入格式
一行，为需要你计算的表达式，表达式中只包含数字、加法运算符“+”和乘法运算符“×”，且没有括号，所有参与运算的数字均为 0 到 2^31−1 之间的整数。
输入数据保证这一行只有
0−9、+、×这 12种字符。
输出格式
一个整数，表示这个表达式的值。
注意：当答案长度多于 4 位时，请只输出最后4 位，前导0 不输出。
输入：
1+1*3+4
输出：
8
注意：scanf()的妙用；
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,num,sum,mul;
char ch,f=0;
bool flag=1;;
int main()
{
while(flag)
{
scanf("%d",&num);
flag=scanf("%c",&ch)==1?true:false;
if(f==0)mul=num;
if(f=='+')sum=(sum+mul)%10000,mul=num;
if(f=='*')mul=(mul*num)%10000;
if(!flag)sum=(sum+mul)%10000;
f=ch;
}
printf("%lld\n",sum);
return 0;
}
京公网安备 11010502036488号