NEFU OJ 大一寒假集训三（暴力枚举）2020.01.02

NEFU OJ 大一寒假集训三（暴力枚举）2020.01.02

Summary

丑数这个是真的暴力 §(￣▽￣)§
第一次一遍过，留个纪念~

Information

No.	Title	AC/Submit
A	二倍的问题	150/233
B	大乐透	143/268
C	密码箱	149/337
D	字符串统计	149/215
E	丑数	27/118
F	矩形	73/110
G	抽奖	129/222
H	比身高	121/184
I	楼层编号	103/253
J	比例简化	34/74
K	奶牛碑文	47/222

Problem A: 二倍的问题 (8) [150/233]

Tips

暴力for套for

Code

#include <bits/stdc++.h>
using namespace std;int main()
{int num[15],ans;int i,n;cin>>n;while(n--){ans=0;for(i=0;i<15;i++){cin>>num[i];if(num[i]==0)break;}for(int j=0;j<i;j++){for(int k=j+1;k<i;k++){if(num[j]==2*num[k]||num[k]==2*num[j])ans++;}}cout<<ans<<endl;}return 0;
}

Problem B: 大乐透 (573) [143/268]

Tips

emm…暴力是无止境的~

Code

#include <bits/stdc++.h>
using namespace std;int main()
{int k,num[1000];while(1){cin>>k;if(k==0)break;for(int i=0;i<k;i++){cin>>num[i];}for(int i=0;i<k;i++){for(int j=i+1;j<k;j++){for(int l=j+1;l<k;l++){for(int m=l+1;m<k;m++){for(int n=m+1;n<k;n++){for(int o=n+1;o<k;o++){printf("%d %d %d %d %d %d\n",num[i],num[j],num[l],num[m],num[n],num[o]);}}}}}}}return 0;
}

Problem C: 密码箱 (572) [149/337]

Tips

[0,9]两个前导0 [10,99]一个前导0

Code

#include <bits/stdc++.h>
using namespace std;int main()
{int n;while(cin>>n){for(int i=n+1;i<1000;i++){if(i<10)printf("0");if(i<100)printf("0");printf("%d\n",i);}}return 0;
}

Problem D: 字符串统计 (193) [149/215]

Tips

简单循环

Code

#include <bits/stdc++.h>
using namespace std;int main()
{int n,ans;char str[101];cin>>n;while(n--){ans=0;cin>>str;for(int i=0;i<strlen(str);i++){if(str[i]>='0'&&str[i]<='9')ans++;}cout<<ans<<endl;}return 0;
}

Problem E: 丑数 (574) [27/118]

暴力打表法，内容较长，详见这篇文章
还有隔壁大佬的代码

Problem F: 矩形 (575) [73/110]

Tips

这个完全被覆盖的矩形是被另一个矩形完全覆盖，不是所有矩形一起覆盖

Code

#include <bits/stdc++.h>
using namespace std;struct sqare
{int minx,maxx;int miny,maxy;
}s[10000]; int main()
{int n,ans,bf[10000]={0};while(cin>>n){ans=0;memset(bf,0,sizeof(bf));for(int i=0;i<n;i++){scanf("%d %d %d %d",&s[i].minx,&s[i].maxx,&s[i].miny,&s[i].maxy);}for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(i==j)continue;if(!bf[j]&&s[i].minx<=s[j].minx&&s[i].maxx>=s[j].maxx&&s[i].miny<=s[j].miny&&s[i].maxy>=s[j].maxy){ans++;bf[j]=1;}if(!bf[i]&&s[j].minx<=s[i].minx&&s[j].maxx>=s[i].maxx&&s[j].miny<=s[i].miny&&s[j].maxy>=s[i].maxy){ans++;bf[i]=1;}}}cout<<ans<<endl;}return 0;
}

Problem G: 抽奖 (1639) [129/222]

Tips

for一下就出来了

Code

#include <bits/stdc++.h>
using namespace std;int main()
{int n,num[100],zj,i;cin>>n;for(i=0;i<n;i++){cin>>num[i];}cin>>zj;for(i=0;i<n;i++){if(num[i]==zj){cout<<i+1;break;}}if(i==n)cout<<0;return 0;
}

Problem H: 比身高 (1640) [121/184]

Tips

人数少，暴力跑 ╰(￣ω￣ｏ)

Code

#include <bits/stdc++.h>
using namespace std;int main()
{int n,num[1000],l,r,ans=0;cin>>n;for(int i=0;i<n;i++){cin>>num[i];}for(int i=0;i<n;i++){l=r=0;for(int j=i-1;j>=0;j--){if(num[j]>num[i])l++;}for(int j=i+1;j<n;j++){if(num[j]>num[i])r++;}if(l==r)ans++;}cout<<ans;return 0;
}

Problem I: 楼层编号 (1642) [103/253]

Tips

已知编号求实际

Code

#include <bits/stdc++.h>
using namespace std;
int m,t,b;int exist(int n)
{while(n>0){b=n%10;n/=10;if(b==t)return 0;}return 1;
}int main()
{int rf=0;cin>>m>>t;for(int i=1;i<=m;i++){if(exist(i))rf++;}cout<<rf;return 0;
}

Problem J: 比例简化 (1643) [34/74]

Tips

A′和 B′ 均不大于 L，且 A′ 和 B′ 互质的前提下
A′/B′ ≥ A/B 且 A′/B′ - A/B 的值尽可能小

Code

#include <bits/stdc++.h>
using namespace std;
int m,t,b;int gcd(int a,int b)
{if(a==0)return b;if(b==0)return a;if(a>b)return gcd(b,a%b);else return gcd(a,b%a);
}int main()
{int a,b,l,tmp,aa,bb;double fs,minoffset=10000000,real;cin>>a>>b>>l;tmp=gcd(a,b);a/=tmp;b/=tmp;real=(double)a/b;if(a<l&&b<l)cout<<a<<" "<<b;else{aa=a;bb=b;for(int i=1;i<=l;i++){for(int j=1;j<=l;j++){if(gcd(i,j)!=1)continue;fs=(double)i/j;if(fs<real)continue;if(fabs(fs-real)<minoffset){minoffset=fabs(fs-real);aa=i;bb=j;}}}cout<<aa<<" "<<bb;}return 0;
}

Problem K: 奶牛碑文 (1644) [47/222]

Tips

Code

#include <bits/stdc++.h>
using namespace std;int main()
{int n;long long c=0,co=0,cow=0;char str[100001];cin>>n>>str;for(int i=0;i<n;i++){if(str[i]=='C')c++;if(str[i]=='O')co+=c;if(str[i]=='W')cow+=co;}cout<<cow;return 0;
}