题目大意:
每次给出三个数x,y,z,用这三个数构成一个等差数列,x为首项,y是末项,z是公差
总共给出n组x,y,z( n待定),求这n组数列中出现次数为奇数的那个数以及该数出现的次数(保证最多有一个数出现的次数为奇数)
首先就是字符串的处理,以及求出n
一直没怎么接触过字符串,一开始根本不知道怎么读入数据,在看了大牛的代码后,知道了sscanf()这个函数神奇的用法,数据读入基本就是copy大牛的代码过来的,
对于最后数据的判断还是不太清楚,不加最后的判断就会wa,还有就是所有的数据最好都用long long,
二分基本上是用的自己的模板,对于这种类型的整数二分,现在写二分终于不再像几天前一样老是出现死循环了
本题二分枚举的mid是出现次数为奇数的数,
采用方法的是对前缀和出现的总次数相加,小于正确值的数都出现偶数次,则当枚举的值小于正确值时,前缀和相加为偶数,
当枚举的值大于等于正确值时,前缀和相加为奇数,sum&1时,ub=mid即可,最后C(ub)-C(ub-1)即可得到mid出现的次数;
/* * Created: 2016年04月03日 20时06分30秒 星期日 * Author: Akrusher * */ #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <ctime> #include <iostream> #include <algorithm> #include <string> #include <vector> #include <deque> #include <list> #include <set> #include <map> #include <stack> #include <queue> #include <numeric> #include <iomanip> #include <bitset> #include <sstream> #include <fstream> using namespace std; #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) #define in(n) scanf("%d",&(n)) #define in2(x1,x2) scanf("%d%d",&(x1),&(x2)) #define in3(x1,x2,x3) scanf("%d%d%d",&(x1),&(x2),&(x3)) #define inll(n) scanf("%I64d",&(n)) #define inll2(x1,x2) scanf("%I64d%I64d",&(x1),&(x2)) #define inlld(n) scanf("%lld",&(n)) #define inlld2(x1,x2) scanf("%lld%lld",&(x1),&(x2)) #define inf(n) scanf("%f",&(n)) #define inf2(x1,x2) scanf("%f%f",&(x1),&(x2)) #define inlf(n) scanf("%lf",&(n)) #define inlf2(x1,x2) scanf("%lf%lf",&(x1),&(x2)) #define inc(str) scanf("%c",&(str)) #define ins(str) scanf("%s",(str)) #define out(x) printf("%d ",(x)) #define out2(x1,x2) printf("%d %d ",(x1),(x2)) #define outf(x) printf("%f ",(x)) #define outlf(x) printf("%lf ",(x)) #define outlf2(x1,x2) printf("%lf %lf ",(x1),(x2)); #define outll(x) printf("%I64d ",(x)) #define outlld(x) printf("%lld ",(x)) #define outc(str) printf("%c ",(str)) #define pb push_back #define mp make_pair #define fi first #define se second #define SZ(x) ((int)(x).size()) #define mem(X,Y) memset(X,Y,sizeof(X)); typedef vector<int> vec; typedef long long ll; typedef pair<int,int> P; const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1}; const ll INF=1ll<<38; //直接用1移位会爆int const ll mod=1e9+7; ll powmod(ll a,ll b) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} const bool AC=true; const int M_case=1000000+100; ll x[M_case],y[M_case],z[M_case];//等差数列,x为首项,y是末项,z是公差 ll cnt; char str[110]; //偶偶偶偶偶偶奇(mid)奇奇奇奇奇 ll C(ll mid){ //返回值用ll,否则会wa ll sum=0,temp; rep(i,0,cnt){ if(mid<x[i]) continue; temp=min(mid,y[i])-x[i]; sum+=temp/z[i]+1; //前缀和出现的次数,包括当前 } return sum ; //奇数为true; } void solve(){ ll lb,mid,ub; lb=1ll,ub=INF; while(ub>lb){ mid=(lb+ub)>>1; if(C(mid)&1) ub=mid; else lb=mid+1; } if(lb==INF) printf("no corruption "); else printf("%lld %lld ",ub,C(ub)-C(ub-1));//计算次数 } int main() { cnt=0; while(gets(str)!=NULL){ if(strlen(str)==0){ if(cnt==0) continue; //注意输入数据之间可能又多行空格 solve(); cnt=0; } else{ sscanf(str,"%I64d%I64d%I64d",&x[cnt],&y[cnt],&z[cnt]); cnt++; } } if(cnt) solve();//必须加上判断,否则会wa return 0; }