本场新生赛和今晚的小白月赛
本次比赛还是暴力了自己很大的问题, 代码量和思维量都明显不够, 只会暴力和找规律, 遇到稍微思维量大一点的
代码题就没办法.
优点是, 比赛完后立马补题, 效果最好.
A - 签到
- #include<iostream>
- #include<stdio.h>
- #include<string.h>
- #include<algorithm>
- #define ll long long
- using namespace std;
- const ll mod = 1e9+7;
- const int maxx = 1e5+7;
- struct node
- {
- ll x,y;
- }p[maxx];
- ll qpow(ll a,ll b)
- {
- ll ans=1;
- while(b)
- {
- if(b&1)
- {
- ans=ans*a%mod;
- }
- a=a*a%mod;
- b/=2;
- }
- return ans;
- }
- int main()
- {
- ll n;
- while(~scanf("%lld",&n))
- {
- for (int i=1; i<=n; i++)
- {
- scanf("%lld%lld",&p[i].x,&p[i].y);
- }
- ll ans=1;
- ll a=1;
- ll b=1;
- for(int i=1; i<=n; i++)
- {
- a=a*(p[i].y-p[i].x)%mod;
- b=b*qpow(p[i].y,mod-2)%mod;
- }
- ans=(1-a*b%mod+mod)%mod;
- printf("%lld\n",ans);
- }
- return 0;
- }
- View Code
本题最开始我想错了, 正解是每层楼掉东西的概率 p[i]=a[i]/b[i], 那么不掉东西的概率应该是
p=sigma((b[i]-a[i])/b[i])
那么掉东西的概率就是 1-p, 那么. 这个题再求逆元, 就很好办了.
B - 法法
- #include<iostream>
- #include<stdio.h>
- #include<string.h>
- #include<algorithm>
- #define ll long long
- int main(){
- int t;
- scanf("%d",&t);
- long long n;
- while(t--){
- scanf("%lld",&n);
- if (n==1 || n==2)printf("1\n");
- else printf("0\n");
- }
- return 0;
- }
- View Code
水题: 特判 1,2 即可
E - 换个角度思考
- #include<iostream>
- #include<stdio.h>
- #include<string.h>
- #include<algorithm>
- using namespace std;
- const int maxx = 1e5+7;
- int n,m,ans[maxx];
- struct node
- {
- int val;
- int id;
- } s[maxx];
- bool cmpnode(node x,node y)
- {
- return x.val<y.val;
- }
- struct Query
- {
- int l,r;
- int h;
- int id;
- } q[maxx];
- bool cmpQuery(Query x,Query y)
- {
- return x.h <y.h;
- }
- int tree[maxx];
- int lowbit(int x)
- {
- return x&(-x);
- }
- void add(int i,int x)
- {
- while(i<maxx)
- {
- tree[i]+=x;
- i+=lowbit(i);
- }
- }
- int sum(int i)
- {
- int sum=0;
- while(i>0)
- {
- sum+=tree[i];
- i-=lowbit(i);
- }
- return sum;
- }
- int query(int l,int r)
- {
- return sum(r)-sum(l-1);
- }
- int main()
- {
- memset(tree,0,sizeof(tree));
- scanf("%d%d",&n,&m);
- for (int i=1;i<=n;i++){
- scanf("%d",&s[i].val);
- s[i].id=i;
- }
- sort(s+1,s+1+n,cmpnode);// 按值进行排序
- for (int i=1;i<=m;i++){
- scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].h);
- q[i].id=i;
- }
- sort(q+1,q+1+m,cmpQuery);// 按照询问的右区间进行排序
- int top=1;// 对于每个值, 如果这个数在某个区间
- for (int i=1;i<=m;i++){
- while(top<=n && s[top].val<=q[i].h)// 这个值小于 x
- {
- add(s[top].id,1);
- top++;
- }
- ans[q[i].id]=query(q[i].l,q[i].r);
- }
- for (int i=1;i<=m;i++){
- printf("%d\n",ans[i]);
- }
- return 0;
- }
- View Code
这个题目数据有问题, 暴力能过....
正解是莫队, 对询问和值进行排序, 然后树状数组维护.
H - 论如何出一道水题
- #include<iostream>
- #include<stdio.h>
- #include<string.h>
- #include<algorithm>
- using namespace std;
- int main(){
- long long n;
- while(~scanf("%lld",&n)){
- if(n==1)printf("2\n");
- else
- printf("%lld\n",2*n-1);
- }
- return 0;
- }
- View Code
水题, MAX(i,j), 且 i,j 互质.
那么问题很简单, i=n-1,j=n, 即可. 但是要特判 1;
来源: http://www.bubuko.com/infodetail-2851275.html