Codeforces Round #450 (Div. 2)

A 

签到

---

 B. Position in Fraction

题意

给a、b、c，问a/b小数点都几位是c，没有输出-1 (a，b<=1e5，0<=c<=9)

分析

这个题，就是烦无限不循环小数，可以大胆猜一下，暴力1e6位，找一下，注意/和%其中关系即可

#include<bits/stdc++.h>
#define de(x) cout<<#x<<"="<<x<<endl;
#define dd(x) cout<<#x<<"="<<x<<" ";
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define repd(i,a,b) for(int i=a;i>=(b);--i)
#define mt(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define inf 0x7f
#define pii pair<int,int>
#define pdd pair<double,double>
#define pdi pair<double,int>
#define mp(u,v) make_pair(u,v)
#define sz(a) a.size()
#define ull unsigned long long
#define ll long long
#define pb push_back
#define PI acos(-1.0)
const int mod = 1e9+7;
const int maxn = 1e5+5;
const double EPS = 1e-6;
using namespace std;


int main()
{
    int a,b,k;
    scanf("%d%d%d", &a, &b, &k);
    a%=b;
    int ans=1000000;
    int c=-1;
    int cnt=0;
    while(ans--)
    {
        cnt++;
        a*=10;
        if(a>=b)
        {
            c=a/b;
            a%=b;
        }
        else 
            c=0;
        if(c==k)
        {
            printf("%d
", cnt);
            return 0;
        }
    }
    printf("-1
");
    return 0;
}

---

C. Remove Extra One

题意

给一个1~n数列，定义一个record：对于位置i，其数字为a[i]，如果对每一个j（1<=j<i）都满足a[j]<=a[i]，那么这个数就为record数字，现在可以删除一个数，使得这个数列的record数最多，输出这个数，如果存在相同数量，输出最小的哪一个

分析

every！！！题意一开始看错了啊（垃圾

看懂了正确的题意，现在开始分析：

设前i个数的最大和次大值分别为max1，max2，考虑位置i：

1，如果a[i]>max1，此时不需要删除任何数，删除max1，会使record-1

2，如果max2<a[i]<max1，此时删除max1，会让record+1

3，如果a[i]<max2，此时这个a[i]，无论怎么删除都不会使得record+1

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
const int maxm=1e5+5;

int n;
int cnt[maxn];
int max1,max2;
int main()
{
    int x;
    scanf("%d", &n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d", &x);
        if(x>max1)
        {
            cnt[x]--;
            max2=max1;
            max1=x;
        }
        else if(x>max2)
        {
            cnt[max1]++;
            max2=x;
        }
    }
    int id=1;
    for(int i=1;i<=n;i++)
    {
        if(cnt[i]>cnt[id])
        {
            id=i;
        }
    }
    printf("%d
", id);
    return 0;
}

---

D. Unusual Sequences

题意

 给两个数x，y，问有多少种序列，使得整个序列的gcd为x，和为y

分析