Description
You are given two positive integers A and B in Base C. For the equation:
We know there always existing many non-negative pairs (k, d) that satisfy the equation above. Now in this problem, we want to maximize k.
For example, A="123" and B="100", C=10. So both A and B are in Base 10. Then we have:
(1) A=0*B+123
(2) A=1*B+23
As we want to maximize k, we finally get one solution: (1, 23)
The range of C is between 2 and 16, and we use 'a', 'b', 'c', 'd', 'e', 'f' to represent 10, 11, 12, 13, 14, 15, respectively.
Input
The first line of the input contains an integer T (T≤10), indicating the number of test cases.
Then T cases, for any case, only 3 positive integers A, B and C (2≤C≤16) in a single line. You can assume that in Base 10, both A and B is less than 2^31.
Output
Sample Input
3 2bc 33f 16 123 100 10 1 1 2
Sample Output
(0,700) (1,23) (1,0)
分析:给两个整数A、B（C进制），根据公式A=k*B+d;求k,d>=0时k最大时的一组解。如果A<B,那么答案是（0,A）。如果A>=B，那么答案是（(int)A/B,A%B）。
#include<iostream> #include<cstdio> #include<string> #include<cmath> using namespace std; __int64 get_num(char *s,int c) { int i,n=strlen(s)-1; __int64 num=0; for(i=n;i>=0;i--) { if('0'<=s[i] && s[i]<='9') num+=(int)pow(c*1.0,(n-i)*1.0)*(s[i]-'0'); else num+=(int)pow(c*1.0,(n-i)*1.0)*(s[i]-'a'+10); } return num; } int main() { int T,C; __int64 A,B; char s1[100],s2[100]; scanf("%d",&T); while(T--) { scanf("%s %s %d",s1,s2,&C); A=get_num(s1,C); B=get_num(s2,C); if(A<B) { printf("(0,%I64d) ",A); } else printf("(%I64d,%I64d) ",A/B,A%B); } return 0; }
Description
Bin has a dream that he and Jing are both in a wonderland full of beautiful gifts. Bin wants to choose some gifts for Jing to get in her good graces.
There are N different gifts in the wonderland, with ID from 1 to N, and all kinds of these gifts have infinite duplicates. Each time, Bin shouts loudly, “I love Jing”, and then the wonderland random drop a gift in front of Bin. The dropping probability for gift i (1≤i≤N) is P(i). Of cause, P(1)+P(2)+…+P(N)=1. Bin finds that the gifts with the higher ID are better. Bin shouts k times and selects r best gifts finally.
That is, firstly Bin gets k gifts, then sorts all these gifts according to their ID, and picks up the largest r gifts at last. Now, if given the final list of the r largest gifts, can you help Bin find out the probability of the list?
Input
The first line of the input contains an integer T (T≤2,000), indicating number of test cases.
For each test cast, the first line contains 3 integers N, k and r (1≤N≤20, 1≤k≤52, 1≤r≤min(k,25)) as the description above. In the second line, there are N positive float numbers indicates the probability of each gift. There are at most 3 digits after the decimal point. The third line has r integers ranging from 1 to N indicates the finally list of the r best gifts’ ID.
Output
Sample Input
4 2 3 3 0.3 0.7 1 1 1 2 3 3 0.3 0.7 1 1 2 2 3 3 0.3 0.7 1 2 2 2 3 3 0.3 0.7 2 2 2
Sample Output
0.027000 0.189000 0.441000 0.343000
题目大意：有N种礼物，每喊一次掉下一个礼物，每个礼物掉下来的概率为pi，呼喊k次,只选取r个编号较大的礼物。
分析：根据排列组合来计算概率，设编号ai有ni个，由于k可能大于r，根据乘法原理它概率分两部分：
第一部分：r个中最小编号（minn）外的概率Power(p[i],m[i])*C(m[i],r)*Power(p[i+1],m[i+1])*C(m[i+1],r-m[i])....;
第二部分：k-r个礼物，有多种情况（最小编号的个数（0，k-r））。可以把小于最小编号的看成一个种礼物(p=sum{pi,i<minn}),根据加法原理计算。
#include<iostream> #include<cstdio> #include<cmath> #include<map> using namespace std; int N,K,R; double p[25]; inline int min(int a,int b){ return a<b?a:b;} double Power(double a,int b) { double ret=1; while(b) { if(b&1) ret=ret*a; a=a*a; b>>=1; } return ret; } __int64 C(int k,int n) { int i; __int64 ans=1; for ( i = 1; i <=k ; i++) { ans*= (n-i+1); ans/=i; } return ans; } int main() { int T,i,temp,Min,kk,rt; double Minp,ans,tp; map<int,int> m; scanf("%d",&T); while(T--) { m.clear(); Min=100;Minp=0;ans=1.0; scanf("%d %d %d",&N,&K,&R); kk=K; for(i=1;i<=N;i++) scanf("%lf",p+i); for(i=1;i<=R;i++){ scanf("%d",&temp);m[temp]++;Min=min(Min,temp);} for(i=1;i<Min;i++) Minp+=p[i]; for(i=Min+1;i<=N;i++) { if(m[i]>0) { ans*=Power(p[i],m[i])*C(m[i],kk); kk=kk-m[i]; } } tp=0; for(i=0;i<=K-R; i++) { rt=K-R-i; tp+=((Power(p[Min],m[Min]+i)*C(m[Min]+i,K-R+m[Min])) * Power(Minp,rt)); } ans*=tp; printf("%.6lf ",ans); } return 0; }
#include<stdio.h> int main() { int n,l,r,t; int sum; scanf("%d",&t); while(t--) { scanf("%d%d%d",&n,&l,&r); sum = 0; for(int i =l;i<=r;i++) { sum +=(int)(n/i*1.0); } printf("%d ",sum); } return 0; }
Description
Given N integers A={A[0],A[1],...,A[N-1]}. Here we have some operations:
Operation 1: AND opn L R
Here opn, L and R are integers.
For L≤i≤R, we do A[i]=A[i] AND opn (here "AND" is bitwise operation).
Operation 2: OR opn L R
Here opn, L and R are integers.
For L≤i≤R, we do A[i]=A[i] OR opn (here "OR" is bitwise operation).
Operation 3: XOR opn L R
Here opn, L and R are integers.
For L≤i≤R, we do A[i]=A[i] XOR opn (here "XOR" is bitwise operation).
Operation 4: SUM L R
We want to know the result of A[L]+A[L+1]+...+A[R].
Now can you solve this easy problem?
Input
The first line of the input contains an integer T, indicating the number of test cases. (T≤100)
Then T cases, for any case, the first line has two integers n and m (1≤n≤1,000,000, 1≤m≤100,000), indicating the number of elements in A and the number of operations.
Then one line follows n integers A[0], A[1], ..., A[n-1] (0≤A[i]<16,0≤i<n).
Then m lines, each line must be one of the 4 operations above. (0≤opn≤15)
Output
Sample Input
1 4 4 1 2 4 7 SUM 0 2 XOR 5 0 0 OR 6 0 3 SUM 0 2
Sample Output
7 18
Hint
A = [1 2 4 7]
SUM 0 2, result=1+2+4=7;
XOR 5 0 0, A=[4 2 4 7];
OR 6 0 3, A=[6 6 6 7];
SUM 0 2, result=6+6+6=18.
//;Write by lk1993, 2014.3.23 #include <stdio.h> #include <string.h> const int M = 1000000 + 5; int sum[M]; inline void pushDown(int rt) { if(sum[rt] >= 0) { sum[rt << 1] = sum[rt << 1 | 1] = sum[rt]; sum[rt] = -1; } } inline void pushUp(int rt) { if(sum[rt << 1] != -1 && sum[rt << 1 | 1] != -1 && sum[rt << 1] == sum[rt << 1 | 1]) { sum[rt] = sum[rt << 1]; } } void build(int l, int r, int rt) { if(l == r) { scanf("%d", &sum[rt]); return ; } int m = (l + r) >> 1; build(l, m, rt << 1); build(m + 1, r, rt << 1 | 1); pushUp(rt); } void update(char op, int val, int ul, int ur, int l, int r, int rt) { if(ul <= l && ur >= r) { if(sum[rt] >= 0) { if('A' == op) sum[rt] &= val; else if('X' == op) sum[rt] ^= val; else if('O' == op) sum[rt] |= val; return ; } } pushDown(rt); int m = (l + r) >> 1; if(ul <= m) { update(op, val, ul, ur, l, m, rt << 1); } if(ur > m) { update(op, val, ul, ur, m + 1, r, rt << 1 | 1); } pushUp(rt); } int query(int ql, int qr, int l, int r, int rt) { if(ql <= l && qr >= r) { if(sum[rt] >= 0) { return sum[rt] * (r - l + 1); } } pushDown(rt); int m = (l + r) >> 1; int ret = 0; if(ql <= m) { ret += query(ql, qr, l, m, rt << 1); } if(qr > m) { ret += query(ql, qr, m + 1, r, rt << 1 | 1); } return ret; } int main(int argc, char* argv[]) { #ifdef __MYLOCAL freopen("in.txt", "r", stdin); #endif int t, n, m, a, b, c; char oper[10]; scanf("%d", &t); while(t--) { scanf("%d%d", &n, &m); memset(sum, -1, sizeof(sum)); build(1, n, 1); while(m--) { scanf("%s", oper); if('S' == oper[0]) { scanf("%d%d", &a, &b); printf("%d ", query(a + 1, b + 1, 1, n, 1)); } else { scanf("%d%d%d", &a, &b, &c); update(oper[0], a, b + 1, c + 1, 1, n, 1); } } } return 0; }
Description
Cao Cao was hunted down by thousands of enemy soldiers when he escaped from Hua Rong Dao. Assuming Hua Rong Dao is a narrow aisle (one N*4 rectangle), while Cao Cao can be regarded as one 2*2 grid. Cross general can be regarded as one 1*2 grid.Vertical general can be regarded as one 2*1 grid. Soldiers can be regarded as one 1*1 grid. Now Hua Rong Dao is full of people, no grid is empty.
There is only one Cao Cao. The number of Cross general, vertical general, and soldier is not fixed. How many ways can all the people stand?
Input
There is a single integer T (T≤4) in the first line of the test data indicating that there are T test cases.
Then for each case, only one integer N (1≤N≤4) in a single line indicates the length of Hua Rong Dao.
Output
Sample Input
2 1 2
Sample Output
0 18
Hint
#include<iostream> #include<cstdio> using namespace std; bool vis[10][10]; int N,ans; void dfs(int i,int j) { if(j>4) { i++;j=1; if(i>N) { ans++;return ; } } if(vis[i][j]) dfs(i,j+1); if(!vis[i][j]) { vis[i][j]=true;dfs(i,j+1);vis[i][j]=false; } if(!vis[i][j] && j+1<=4 && !vis[i][j+1]) { vis[i][j]=vis[i][j+1]=true; dfs(i,j+2); vis[i][j]=vis[i][j+1]=false; } if(!vis[i][j] && i+1<=N && !vis[i+1][j]) { vis[i][j]=vis[i+1][j]=true; dfs(i,j+1); vis[i][j]=vis[i+1][j]=false; } return ; } int main() { int T,i,j; scanf("%d",&T); while(T--) { scanf("%d",&N); ans=0; for(i=1;i<N;i++) { for(j=1;j<4;j++) { memset(vis,false,sizeof(vis)); vis[i][j]=vis[i][j+1]=vis[i+1][j]=vis[i+1][j+1]=true; dfs(1,1); } } printf("%d ",ans); } return 0; }
#include<cstdio> #include<cmath> #include<algorithm> using namespace std; typedef __int64 LL ; struct Point { LL x, y; Point(LL x=0, LL y=0):x(x),y(y) { } }p[105]; typedef Point Vector; Vector operator + (const Vector& A, const Vector& B) { return Vector(A.x+B.x, A.y+B.y); } Vector operator - (const Point& A, const Point& B) { return Vector(A.x-B.x, A.y-B.y); } Vector operator * (const Vector& A, double p) { return Vector(A.x*p, A.y*p); } double Dot(const Vector& A, const Vector& B) { return A.x*B.x + A.y*B.y; } double Cross(const Vector& A, const Vector& B) { return A.x*B.y - A.y*B.x; } double Length(const Vector& A) { return sqrt(Dot(A, A)); } Point read_point() { Point a; scanf("%I64d %I64d",&a.x,&a.y); return a; } bool is_ok(int i,int j,int k) { bool flag=1; if(0-Dot(p[j]-p[i],p[k]-p[i])>0.0000001) flag=0; if(0-Dot(p[j]-p[k],p[i]-p[k])>0.0000001) flag=0; if(0-Dot(p[i]-p[j],p[k]-p[j])>0.0000001) flag=0; return flag; } int main() { int T,i,n,j,k,ans; scanf("%d",&T); while(T--) { scanf("%d",&n); for(i=0;i<n;i++) p[i]=read_point(); ans=0; for(i=0;i<n;i++) { for(j=i+1;j<n;j++) { for(k=j+1;k<n;k++) { if(is_ok(i,j,k)) ans++; } } } printf("%d ",ans); } return 0; }
#include<iostream> #include<cstring> #include<cstdio> using namespace std; int len,findex; char s[1010]; struct node { char ch; int x; }t; void find_min1() { t.ch='9';t.x=len; for(int j=len-1;j>findex;j--) { if(s[j]<s[findex] && s[j]<=t.ch) { t.ch=s[j]; t.x=j; } } } void find_min2() { t.ch='9';t.x=len; for(int j=len-1;j>findex;j--) { if(s[j]<s[findex] && s[j]<=t.ch && s[j]>'0') { t.ch=s[j]; t.x=j; } } } void Swap(int i,int j) { char ch=s[i]; s[i]=s[j];s[j]=ch; } int main() { int T,n,i; scanf("%d",&T); while(T--) { scanf("%s %d",s,&n); len=strlen(s); findex=0; for(i=0;i<n;) { if(findex==len-1) break; find_min1(); if(findex==0 && t.ch=='0') find_min2(); if(t.x==len) { findex++; continue; } else { Swap(findex,t.x); findex++;i++; } } printf("%s ",s); } return 0; }