原諒我就只會這兩水題了，其他題沒怎麼看~估計看了也是無奈
Olympiad
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 234 Accepted Submission(s): 171
Problem Description
[a,b] (a≤b). Please be fast to get the gold medal!
Input
T (T≤1000), indicating the number of testcases.
For each test case, there are two numbers a and b, as described in the statement. It is guaranteed that 1≤a≤b≤100000.
Output
For each testcase, print one line indicating the answer.
Sample Input
2 1 10 1 1000
Sample Output
10 738
Author
XJZX
Source
2015 Multi-University Training Contest 4
Recommend
wange2014
1001：
beautiful numbers的定義：就是一個數的每一位不能有相同的數字，現在給你一個區間，讓你求這區間內有多少個這樣的漂亮數
思路方法：打表，預處理前n個數有多少個漂亮數，然後求解時直接輸出
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#define N 100010
typedef long long LL;
using namespace std;
int p[N],a[12];
void init(){
p[0]=0;
for(int i=1;i<100010;i++){
int ok=1;
memset(a,0,sizeof(a));
int x=i;
while(x){
//cout<<x<<endl;
a[x%10]++;
x/=10;
}
for(int j=0;j<10;j++){
if(a[j]>=2) ok=0;
}
if(ok) p[i]=p[i-1]+1;
else p[i]=p[i-1];
}
}
int main(){
init();
int T;
scanf("%d",&T);
while(T--){
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",p[r]-p[l-1]);
}
return 0;
}
Problem Killer
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 470 Accepted Submission(s): 194
Problem Description
You are a "Problem Killer", you want to solve many problems.
Now you have n problems, the i-th problem's difficulty is represented by an integer ai ( 1≤ai≤109).
For some strange reason, you must choose some integer l and r ( 1≤l≤r≤n), and solve the problems between the l-th and the r-th, and these problems' difficulties must form an AP (Arithmetic Progression) or a GP (Geometric Progression).
So how many problems can you solve at most?
You can find the definitions of AP and GP by the following links:
https://en.wikipedia.org/wiki/Arithmetic_progression https://en.wikipedia.org/wiki/Geometric_progression
Input
T, indicating the number of cases.
For each test case, the first line contains a single integer n, the second line contains n integers a1,a2,⋯,an.
T≤104,∑n≤106
Output
For each test case, output one line with a single integer, representing the answer.
Sample Input
2 5 1 2 3 4 6 10 1 1 1 1 1 1 2 3 4 5
Sample Output
4 6
Author
XJZX
Source
2015 Multi-University Training Contest 4
Recommend
wange2014 | We have carefully selected several similar problems for you: 5338 5337 5336 5335 5334
題意：在一個長度為n的序列中取出連續的k個數，讓這k個數組成等差數列或者等比數列，問這樣的k最大可以是多少。
思路方法：當時和幾個隊友在討論，然後他們在討論暴力n^2是否會超時，結果時肯定的。然後我的第一想法是想到用前n相和去枚舉判斷，然後可以通過每次求到的k的大小去去除後面無須判斷的數據，然後算了下複雜度是介於n~n方，當時以為是不會超的，然後還是太年輕。。後來後來就發現其實是可以先開出兩個數組，算出每一項與前一項的公差和公比，然後就會發現，此題就可以轉化為求最長相同的子序列,複雜度為O(n)。（！！注：C++ TLE，G++ AC，不要問我為什麼，我也不知道）
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#define N 1000010
#define eps 1e-8
#define INF 0x3f3f3f3f
typedef long long LL;
using namespace std;
double a[N],b[N],c[N];
int main(){
int T,n;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lf",&c[i]);
}
if(n==0||n==1||n==2){
printf("%d\n",n);
continue;
}
for(int i=2;i<=n;i++){
a[i]=c[i]-c[i-1];
b[i]=c[i]/c[i-1];
}
a[1]=b[1]=INF;
int ans=2;
double t=a[1],tot=0;
for(int i=1;i<=n;i++){
if(fabs(a[i]-t)<=eps){
tot++;
}else{
tot=1;
t=a[i];
}
if(ans<tot+1) ans=tot+1;
}
t=a[1],tot=0;
for(int i=1;i<=n;i++){
if(fabs(b[i]-t)<=eps){
tot++;
}else{
tot=1;
t=b[i];
}
if(ans<tot+1) ans=tot+1;
}
printf("%d\n",ans);
}
return 0;
}