1.章鱼王
#include<stdio.h>
using namespace std;
int main(){
int n;
int i=0;
scanf("%d",&n);
int num[n];
while(n--){
scanf("%d",&num[i++]);
}
int j=0;
while(i--){
printf("%d\n",num[j++]/3);
}
}
2.拥塞的城市
//原始思路，用数组存入随着偏离中心每楼层数 运行时间3.0s超时
#include<stdio.h>
using namespace std;
int main(){
int T;
int sum=0;
int level;
scanf("%d",&T);
while(T--){
int a[level];
a[1]=4;
int j=2;
for(;j<=level;j++){
a[j]=a[j-1]+8;
}
int index=1;
while(level>0){
sum+=(level*(4+8*index));
level--;
}
printf("%d\n",sum);
sum=0;//因为sum为全局作用域
}
}
//改进，不用数字，直接计算 0.05s
#include<stdio.h>
using namespace std;
int main(){
int T;
int level;
scanf("%d",&T);
while(T--){
int sum=0;
scanf("%d",&level);
sum+=level*4;
int index=1;
while(level>1){
sum+=(--level)*(4+(index++)*8);
}
printf("%d\n",sum);
}
3.求100-200素数
#include<iostream>
#include<math.h>
using namespace std;
bool isPrime(int num){
int i=2;
for(;i<=(int)sqrt(num);i++){
if(num%i==0){
return false;
}
}
return true;
}
int main(){
int j=100;
for(;j<=200;j++){
if(isPrime(j)){
cout<<j<<" ";
}
}
}
4.母牛生小牛问题
#include<iostream>
using namespace std;
int main(){
int a[51];//要大于50后面有测试点求第50年
int i=4;
a[1]=1;
a[2]=1;
a[3]=1;
for(;i<=50;i++){//这里等于，太菜了！
a[i]=a[i-1]+a[i-3];
}
while(1){
int years=0;
cin>>years;
if(years==0) break;
cout<<a[years]<<endl;
}
}
5.已知各点坐标求面积
-
本质上是数学题目，为什么题目按逆时针给出点的坐标，目的是让你考虑用有向面积的方法就是用向量的方法表示各点，这里就有公式了，如下图所示，具体证明不懂。。。。
#include<iostream>
using namespace std;
struct P{
int x;
int y;
}p[101];
int area(int a){
int b=a-1;
//可以理解上图的A点是p[0],B点是p[b],C点是p[a],就是AB向量与AC向量的叉积
return (p[b].x-p[0].x)*(p[a].y-p[0].y)-(p[b].y-p[0].y)*(p[a].x-p[0].x);
}
int main(){
int n;
while(cin>>n){
if(n==0) break;
int j=0;
for(;j<n;j++){
cin>>p[j].x;
cin>>p[j].y;
}
int k=2;
double sum=0;
for(;k<n;k++){
sum+=1.0/2.0*area(k);//公式，把多边形每块三角形相加
}
printf("%.1lf",sum);
}
}
########################################################
-
第二种方法(目前而言错误)
第二种方法，我自己考虑的，可以求出在四轴方向延伸最远的点，然后形成矩形，得到四点即角坐标并计算与多边形两点边的距离(两点确定一条边)，从而计算点与边直线距离(高)，最终计算出三角形面积，用形成的矩形减去把所有三角面积和就是多边形面积。
6.回文串
-
题目虽然简单，但是我没写出来，菜….
//采用的是从两边向内策略，比较两边数字大小，小的一边加上后一位，相等则两者靠拢 #include<iostream> #include<vector> using namespace std; vector<long long> v(1000010);//如果用int的话，可能相加会超出int范围，会卡在66测试点 int main(){ int n; cin>>n; for(int j=0;j<n;j++){ cin>>v[j]; } int cnt=0; int i=0,j=n-1; while(i<j){//注意这里结束条件，只采用了两个指针，而不是我的四个指针 long long left=v[i]+v[i+1]; long long right=v[j]+v[j-1]; if(v[i]==v[j]){ i++; j--; }else if(v[i]<v[j]){ v[i+1]=left; i++; cnt++; }else if(v[i]>v[j]){ v[j-1]=right; j--; cnt++; } } cout<<cnt<<endl; }
7.4000以内的完美数
#include<iostream>
#include<vector>
#include <string.h>
#include<math.h>
using namespace std;
//vector<char> v(2000);
char v[4010];
bool isPrime(int a){
for(int j=2;j<=(int)sqrt(a);j++){
if(a%j==0) return false;
}
return true;
}
int main(){
int i=2;
while(i<=4000){
if(!isPrime(i)){
int sum=0;
for(int j=1;j<i;j++){
if(i%j==0){
v[j]='1';
sum+=j;
}
}
if(sum==i){
cout<<i<<" its factors are 1 ";
for(int k=2;k<i;k++){
if(v[k]=='1'){
cout<<k<<" ";
}
}
cout<<endl;
}
}
memset(v,0,sizeof(v));//string.h,只能针对的是char数组初始化
i++;
}
}
8.区间内素数
//0.3s
#include<iostream>
#include<cmath>
#include<memory.h>
using namespace std;
bool isPrime(int n){
for(int i=2;i<=(int)sqrt(n);i++){
if(n%i==0){
return false;
}
}
return true;
}
int main(){
int num=1000001;
bool ispri[num];
memset(ispri,false,sizeof(ispri));
for(int j=2;j<num;j++){
if(isPrime(j)==true){
ispri[j]=true;
}
}
// for(int L=2;L<=10;L++){
// cout<<ispri[L]<<endl;
// }
// cout<<"-------------"<<endl;
int n1,n2;
while(cin>>n1>>n2){
int cnt=0;
for(int k=n1;k<=n2;k++){
if(ispri[k]==true){
cnt++;
}
}
cout<<cnt<<endl;
}
}
------------------------------------------------------------------------
//优化下，显然素数都是奇数0.18s
#include<iostream>
#include<cmath>
#include<memory.h>
using namespace std;
bool isPrime(int n){
for(int i=3;i<=(int)sqrt(n);i+=2){
if(n%i==0){
return false;
}
}
return true;
}
int main(){
int num=1000001;
bool ispri[num];
memset(ispri,false,sizeof(ispri));
//ispri[1]=true;
ispri[2]=true;
for(int j=3;j<num;j+=2){
if(isPrime(j)==true){
ispri[j]=true;
}
}
// for(int L=2;L<=10;L++){
// cout<<ispri[L]<<endl;
// }
// cout<<"-------------"<<endl;
int n1,n2;
while(cin>>n1>>n2){
int cnt=0;
int k;
for(k=n1;k<=n2;k++){
if(ispri[k]==true){
cnt++;
}
}
cout<<cnt<<endl;
}
}
------------------------------------------------------------------------
一些更加聪明的程序猿，会发现一个问题：尝试从 3 到√x 的所有奇数，还是有些浪费。比如要判断101是否质数，101的根号取整后是10，那么，按照境界4，需要尝试的奇数分别是：3，5，7，9。但是你发现没有，对9的尝试是多余的。不能被3整除，必然不能被9整除……顺着这个思路走下去，这些程序猿就会发现：其实，只要尝试小于√x 的质数即可。而这些质数，恰好前面已经算出来了（是不是觉得很妙？）
------------------------------------------------------------------------
//线性筛选法
#include<iostream>
using namespace std;
int n=1000000;
bool prime[1000005]; //一开始都认为是质数（初始化为0），0代表是质数，1代表不是
void ai_shai(){
prime[1]=1; //1不是质数
for(int i=2;i<=1000;++i){//着重这个1000！
if(prime[i]==0){ //如果是质数
for(int j=i*i;j<=n;j+=i){ //从i*i开始筛选 因为2*i~(i-1)*i 之前已被2~(i-1)筛出来了
prime[j]=1;
} //质数的倍数都不是质数
}
}
}
int main(){
ai_shai();
int n1,n2,cnt=0;
// for(int L=0;L<100;L++){
// cout<<prime[L]<<endl;
// }
// cout<<"_-------"<<endl;
while(cin>>n1>>n2){
int cnt=0;
for(int k=n1;k<=n2;k++){
if(prime[k]==0){
cnt++;
}
}
cout<<cnt<<endl;
}
}
------------------------------------------------------------------------
//别人优秀0.012s，用筛法求：https://www.cnblogs.com/lidasu/p/11046109.html
#include<cstdio>
const int N=1000001;
int o[N],p[N],c,x,y;
bool n[N];
int main() {
n[1]=0;
for(int i=2;i<N;i++) {
p[i]=p[i-1];
if(!n[i])
p[i]++,o[c++]=i;
for(int j=0;j<c&&i*o[j]<N;j++) {
n[i*o[j]]=1;
if(i%o[j]==0)
break;
}
}
while(~scanf("%d%d",&x,&y))printf("%d\n",p[y]-p[x-1]);
}
- 筛选法图解~盗图
9.求序列中连续序列最大值
//我的垃圾代码 4.5s
#include<bits/stdc++.h>
using namespace std;
//queue<int> q;
int main(){
int T,N;
cin>>T;
while(T--){
cin>>N;
int a[N];
long long max=-200000000;
//求出数组单个的最大值
for(int i=0;i<N;i++){
cin>>a[i];
if(max<a[i]){
max=a[i];
}
}
for(int j=2;j<N;j++){
int cur=0;
for(int L=0;L<N-j+1;L++){
long long all=0;
int k=cur;
for(;k<j+cur;k++){
all+=a[k];
}
cur++;
if(max<all){
max=all;
}
// all+=a[k];
}
}
//可能序列为全部
int sum=0;
for(int x=0;x<N;x++){
sum+=a[x];
}
if(sum>max)
max=sum;
cout<<max<<endl;
}
}
//大佬代码 0.4 建议看这位大佬讲解：https://www.cnblogs.com/dddyyy/p/10746769.html
//https://www.cnblogs.com/conw/p/5896155.html
#include <stdio.h>
int main()
{
int t,n,m,sum,a;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
sum=0;
m=-9999;
//关键是这里的while循环功能不好理解
while(n--)
{
scanf("%d",&a);
sum+=a;
if(sum>m) m=sum;
if(sum<0) sum=0;
}
printf("%d\n",m);
}
return 0;
}
10.字符串替换
#include<bits/stdc++.h>
#define N 80
using namespace std;
char *replace(char *str,char *oldstr,char *newstr){
char bstr[strlen(str)+1000];//转换缓冲区
memset(bstr,0,sizeof(bstr));
for(int i = 0;i < strlen(str);i++){
if(!strncmp(str+i,oldstr,strlen(oldstr))){//查找目标字符串，在str中找older
strcat(bstr,newstr);//匹配了就将newstr加入缓冲区
i += strlen(oldstr) - 1;//更新指针
}else{
strncat(bstr,str + i,1);//保存一字节进缓冲区，没匹配将str的未匹配第一位移动到bstr
}
}
strcpy(str,bstr);
return str;
}
int main(void)
{
char s[3 * N + 1], x[N + 1], y[N + 1];
scanf("%s%s%s", s, x, y);
replace(s, x, y);
printf("%s\n", s);
return 0;
}
