Problem A:Coins
原题地址
题目大意：有无数个1到n价值的硬币，用这些硬币来凑出S，求需要硬币的最少数目。
分析：这是一道非常明显的贪心题，我们只需要在每次拿取的时候都拿最大的，一直到最后一次，可以刚好拿到最大的或者一个比n小的硬币，这就是硬币数目最少的情况。
但需要注意数据类型，小心溢出。1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main()
{
long long n,s;
scanf("%lld%lld",&n,&s);
long long t=0;
t=s/n;
if(s%n==0)
{
printf("%lld",t);
}
else printf("%lld",t+1);
return 0;
}
Problem B:Views Matter
原题地址
题目大意，我们需要从这些方块中抽出一部分方块，使从右侧往左和从上往下所看到的样子不变，并且要使保留的方块最少。
分析：我们希望使用的方块最少，且两个方向看到的不变，那么我们脑子里首先想到的应该是斜对角线，于是顺着这个思路去找，我们希望能在图形中找到一条类似斜对角线这样，每一个方块都贡献非常高的取法。因此它一定是递增或者递减的，所以我们的第一步就知道了，排序。从最小的那一列开始，在下一列优先取右上方的那一个方块（向着对角线的方向走），但如果右上方没有，那就只能继续水平向右走······走到了最后一列，但我们就需要考虑，从右侧的视角是由什么决定的，就是由最高的那一列决定，因此最后一列上方的也都全部要保留。总-保留=拿走。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
using namespace std;
bool compare(long long x,long long y)
{
return x<y;
}
long long a[100010];
int main()
{
long long n,m;
cin>>n>>m;
long long sum=0;
for(int i=0;i<n;i++)
{
cin>>a[i];
sum+=a[i];
}
sort(a,a+n,compare);
long long hang=0;
long long t=0;
for(int i=0;i<n;i++)
{
if(a[i]>hang)
{
t++;
hang++;
}
else t++;
}
t+=a[n-1]-hang;
cout<<sum-t;
return 0;
}
Problem C:Vasya and Book
原题地址
题目大意：书本一共有n页，想要从x页翻到y页，但是每次只能翻d页，当遇到第一页或最后一页时只能停留这两页，无论d是多少，都不能超过这两页。
分析：根据下面给出的测试数据可以总结出三种情况：1.x可以直接翻到y（y-x能被d整除）2.x通过1中转翻到y（y-1能被d整除）3.x通过n中转翻到y（n-y能被d整除）
注意以下几点：1.x与y的大小关系不确定 2.是否存在既能从1中转也能从n中转的情况。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
using namespace std;
int main()
{
int T;
scanf("%d",&T);
long long n,x,y,d;
long long a,b;
while(T--)
{
a=0;
b=0;
cin>>n>>x>>y>>d;
if((y-x)%d==0)
{
cout<<abs((x-y)/d)<<endl;
}
else
{
if((y-1)%d==0)
{
a=(x-1)/d+1;
a+=(y-1)/d;
}
if((n-y)%d==0)
{
b=(n-x)/d+1;
b+=(n-y)/d;
}
if(a==0&&b==0)
{
cout<<-1<<endl;
}
else
{
if(a==0)
cout<<b<<endl;
if(b==0)
cout<<a<<endl;
if(a!=0&&b!=0)
{
cout<<min(a,b)<<endl;
}
}
}
}
return 0;
}
Problem D:Vova and Trophies
原题地址
这个题没有做出来，因为一直是把目光放在了G上，所以考虑的情况越来越多，到最后就乱成一团（自闭了），看了刘凯同学的题解以后才有了思路，我们可以把目光放在S上面，把S-S-S看作一个整体（‘-’中的G可有可无），将每一个S的位置储存起来，为了保证所有的G都是处于一个整体之中，我们便在开头和结尾都加上一个S。构建完之后进行分类讨论，便会发现，从一开始的好多种情况变成了现在的三种。
1.只有一个三元组（即有三个s）
2.只有一个全为G的组（即有两个S）
3.有多个三元组
前两种的G都非常好求，只有第三种需要仔细斟酌
我们从第一个三元组即s[2]开始看，每个三元组存在两种情况，有其他的G可以补进来(s[i]-s[i-2]-1)，没有其他的G，只能自己组内补（s[i]-s[i-2]-2），而判断有没有其他的G元素（总长度-三元组长度-所有S的个数+3（因为在三元组中有3个S了）是不是为0）.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
using namespace std;
vector<int>s;
int main()
{
int n;
cin>>n;
char a;
int Max=0;
s.push_back(0);
for(int i=1;i<=n;i++)
{
cin>>a;
if(a=='S')
{
s.push_back(i);
}
}
s.push_back(n+1);
if(s.size()==2)
{
cout<<n;
}
else if(s.size()==3)
{
cout<<n-1;
}
else
{
for(int i=2;i<(int)s.size();i++)
{
if((n+2-(s[i]-s[i-2]+1)-s.size()+3)!=0)
Max=max(Max,s[i]-s[i-2]-1);//有其他的G
else
Max=max(Max,s[i]-s[i-2]-2);//没有其他的G
}
cout<<Max;
}
return 0;
}
