只做了4题水题ADGI
A题需要注意的就是“[...]”的输出了，何时输出，何时不输出。
#include <stdio.h>
int main()
{
int n, cur, d;
int cnt = ;
while(scanf("%d%d%d",&n,&cur,&d)!=EOF)
{
printf("Case #%d: ",cnt++);
if(cur==)
printf("[<<]");
else
printf("(<<)");
int start = cur - d;
int end = cur + d;
if(start > && start!= && cur!=)//说明前面有隐藏页，需要输出[...]
printf("[...]");
for(int i=start; i<=end && i<=n; ++i)
{
if(i <= )
continue;
else
{
if(i == cur)
printf("[%d]",i);
else
printf("(%d)",i);
}
}
if(end<n && cur!=n)//说明后面有隐藏页，需要输出[...]
printf("[...]");
if(cur==n)
printf("[>>]");
else
printf("(>>)");
printf("\n"); }
}
D题应该是数学题吧（分步计数原理），将数组weight 和数组pow排序
然后分别判断每个数有多少种选择，然后一一相乘取模
对于第一个hero，如果有a1把剑的weight小于等于power，对于第二个hero，有a2把剑的weight小于等于power,一次类推
那么第一个英雄有a1种选择，第二个英雄有a2-1种选择，第三个英雄有a3-2种选择，一次类推。
至于判断有多少把剑的weight小于每个英雄的power，普通查找会超时，要用二分查找。
二分查找的特性是，对于key，如果数组中有元素与之相等，那么就返回该元素的下标，不然就返回就返回第一个比key大的元素的下标（如果有的话）
如果没有，就返回数组最后一个元素的下标。 所以我们可以用二分查找找出比power[i]小的weight有多少个
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = + ;
const int MOD = ;
int w[N];
int p[N];
void input(int &x)
{
char ch = getchar();
while(ch<'' || ch >'')
ch = getchar();
x = ;
while(ch>='' && ch<='')
{
x = x * + ch - '';
ch = getchar();
}
}
int main()
{
int t;
int n;
int i,j,k,z;
int tCase = ;
input(t);
while(t--)
{
printf("Case #%d: ",tCase++);
input(n);
for(i=; i<=n; ++i)
input(w[i]);
for(i=; i<=n; ++i)
input(p[i]);
sort(w+, w+n+);
sort(p+, p+n+);
LL ans = ;
int cnt;
for(i=; i<=n; ++i)
{
cnt = ;
int low = ; int high = n;
int mid;
while(low <= high)
{
mid = (low + high)/;
if(p[i] == w[mid])
break;
else if(p[i] >= w[mid])
low = mid + ;
else
high = mid - ;
}
if(p[i] < w[mid])
mid--;
ans = (ans*(mid-i+))%MOD;
}
printf("%lld\n",ans);
}
}
G题要没什么，先用字符串读入，判断有没有可能爆，如果有可能，继续进一步的字符串判断，如果没可能，就用sscanf读入，然后判断范围
#include <iostream>
#include <stdio.h>
#include <string>
using namespace std;
typedef long long LL;
string Max = "";//
int main()
{
int i;
string str;
LL num;
while(cin>>str)
{
if(str[] != '-')
{
if(str.size() < )
{
sscanf(str.c_str(),"%lld",&num);
if(num <= )
puts("short");
else if(num <= )
puts("int");
else
puts("long long");
}
else if(str.size()==)
{
if(str > Max)
puts("It is too big!");
else
puts("long long");
}
else
puts("It is too big!");
}
else
{
if(str.size() < )
{
sscanf(str.c_str(),"lld",&num);
if(num >= -)
puts("short");
else if(num >= )
puts("int");
else
puts("long long"); }
else if(str.size() == )
{
str.erase(str.begin());
if(str > Max)
puts("It is too big!");
else
puts("long long");
}
else
puts("It is too big!"); }
}
}
I题要注意的就是最大公约数可能是负数的情况，导致负号出现在分母。应该处理一下再输出。
#include <stdio.h>
const int N = + ;
int gcd(int n, int m)
{
if(m == )
return n;
return gcd(m,n%m);
}
int main()
{
int n, i;
int coe,exp;
while(scanf("%d",&n)!=EOF)
{
for(i=; i<n; ++i)
{
scanf("%d%d",&coe,&exp);
if( coe % (exp+)==)
printf("%d %d ",coe / (exp+),exp+);
else
{
int g = gcd(coe, exp+);
if(g>)
printf("%d/%d %d ",coe/g,(exp+)/g, exp+);
else
printf("%d/%d %d ",-coe/g,-(exp+)/g, exp+); }
}
scanf("%d%d",&coe,&exp);
if( coe % (exp+)==)
printf("%d %d\n",coe / (exp+),exp+);
else
{
int g = gcd(coe, exp+);
if(g>)
printf("%d/%d %d\n",coe/g,(exp+)/g, exp+);
else
printf("%d/%d %d\n",-coe/g,-(exp+)/g, exp+);
}
}
}
J题如果正向模拟，i要不断回溯，导致复杂度时间复杂是O(n*m).但是如果是逆向模拟，i不用回溯，时间复杂度是O(n+m).
#define _CRT_SECURE_NO_DEPRECATE
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = + ;
struct node
{
int val;
int index;
bool operator<(const node &rhs)const
{
return val > rhs.val;
}
}a[N];
int hash[N];
int ans[N];
int op[N];
int main()
{
int t,n,m,tCase = ,i,j;
scanf("%d",&t);
while(t--)
{
memset(hash,,sizeof(hash));
scanf("%d%d",&n,&m);
for(i=; i<n; ++i)
{
scanf("%d",&a[i].val);
a[i].index = i;
}
sort(a,a+n);
for(i=; i<m; ++i)
scanf("%d",&op[i]);
int cnt = ;
printf("Case #%d: ",tCase++);
for(i=,j=m-;j>=;--j)
{
for(; i<n; ++i)
{
if(a[i].val <= op[j])
break;
int index = a[i].index;
hash[index] = true;
if(!hash[index-] && !hash[index+])//如果下标的左右都没有被标记过，则该下标自成一块
cnt++;
else if(hash[index-] && hash[index+])//因为该下标的加入，导致该下标的左右连在一起，2变1
cnt--;
}
ans[j] = cnt;
}
for(i=; i<m-; ++i)
printf("%d ",ans[i]);
printf("%d\n",ans[m-]); }
}