# 2019 HDU多校第九场

## Rikka with Cake

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)

Problem Description

Rikka's birthday is on June 12th. The story of this problem happens on that day.

Today is Rikka's birthday. Yuta prepares a big cake for her: the shape of this cake is a rectangular of n centimeters times m centimeters. With the guidance of a grimoire, Rikka is going to cut the cake.

For simplicity, Rikka firstly builds a Cartesian coordinate system on the cake: the coordinate of the left bottom corner is (0,0) while that of the right top corner is (n,m). There are K instructions on the grimoire: The ith cut is a ray starting from (xi,yi) while the direction is Di. There are four possible directions: L, passes (xi−1,yi); R, passes (xi+1,yi); U, passes (xi,yi+1); D, passes (xi,yi−1).

Take advantage of the infinite power of Tyrant's Eye, Rikka finishes all the instructions quickly. Now she wants to count the number of pieces of the cake. However, since a huge number of cuts have been done, the number of pieces can be very large. Therefore, Rikka wants you to finish this task.
InputThe first line of the input contains a single integer T(1≤T≤100), the number of the test cases.

For each test case, the first line contains three positive integers n,m,K(1≤n,m≤109,1≤K≤105), which represents the shape of the cake and the number of instructions on the grimoire.

Then K lines follow, the ith line contains two integers xi,yi(1≤xi<n,1≤yi<m) and a char Di∈{'L','R','U','D'}, which describes the ith cut.

The input guarantees that there are no more than 5 test cases with K>1000, and no two cuts share the same x coordinate or y coordinate, i.e., ∀1≤i<j≤K, xi≠xjand yi≠yj.
OutputFor each test case, output a single line with a single integer, the number of pieces of the cake.

Hint
The left image and the right image show the results of the first and the second test case in the sample input respectively. Clearly, the answer to the first test case is 3while the second one is 5.

Sample Input

2
4 4 3
1 1 U
2 2 L
3 3 L
5 5 4
1 2 R
3 1 U
4 3 L
2 4 D

Sample Output

3
5

#### 矩形数就是多出来的交点数，用线段树去维护一下一维的交点信息就好了

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define delf int mid=(l+r)>>1
typedef long long ll;
const int maxn=(int)2e5+100;
int ls1[maxn],ls2[maxn],rt[maxn],siz,n,m,k,cnt1,cnt2,tot1,tot2;
ll tmp;
map<char,int> mp;
struct hen{
int xx,hei1,hei2;
}Y[maxn];
struct shu{
int hh,x1,x2;
bool operator<(const shu &b)const{
return hh<b.hh;
}
}X[maxn];
struct Tree{int l,r;ll val;} tree[maxn*80];
void update(int &x,int y,int ql,int qr,int l,int r){
tree[x=(++siz)]=tree[y];
if(ql<=l&&r<=qr){
tree[x].val=tree[y].val+1; return;
}
delf;
if(ql<=mid) update(tree[x].l,tree[y].l,ql,qr,l,mid);
if(qr>mid) update(tree[x].r,tree[y].r,ql,qr,mid+1,r);
}
void query(int x,int y,int pos,int l,int r){
tmp+=tree[y].val-tree[x].val;
if(l==r) return;
delf;
if(pos<=mid) return query(tree[x].l,tree[y].l,pos,l,mid);
else return query(tree[x].r,tree[y].r,pos,mid+1,r);
}
void LS(){
sort(ls1+1,ls1+tot1+1);sort(ls2+1,ls2+tot2+1);
tot1=unique(ls1+1,ls1+tot1+1)-ls1-1;
tot2=unique(ls2+1,ls2+tot2+1)-ls2-1;
sort(X+1,X+cnt2+1);
rep(i,1,cnt2){
X[i].x1=lower_bound(ls1+1,ls1+tot1+1,X[i].x1)-ls1;
X[i].x2=lower_bound(ls1+1,ls1+tot1+1,X[i].x2)-ls1;
X[i].hh=lower_bound(ls2+1,ls2+tot2+1,X[i].hh)-ls2;
}
}
void solve(){
siz=0;cnt1=0;cnt2=0;tot1=0;tot2=0;
ll ans=0;
scanf("%d%d%d",&n,&m,&k);
rep(i,1,k){
int x,y;char op[2];scanf("%d%d%s",&x,&y,op);
ls1[++tot1]=x;
if(op[0]=='L') X[++cnt2]={y,1,x},ls2[++tot2]=y;
if(op[0]=='R') X[++cnt2]={y,x,n},ls2[++tot2]=y;
if(op[0]=='U') Y[++cnt1]={x,y,m};
if(op[0]=='D') Y[++cnt1]={x,1,y};
}
ls1[++tot1]=n;ls2[++tot2]=m;ls1[++tot1]=1;
LS();
rep(i,1,cnt2) update(rt[X[i].hh],rt[X[i].hh-1],X[i].x1,X[i].x2,1,tot1);
rep(i,1,cnt1){
int l,r;
if (Y[i].hei1==1){
l=1,r=lower_bound(ls2+1,ls2+tot2+1,Y[i].hei2)-ls2;
if(ls2[r]>Y[i].hei2) --r;
}
if (Y[i].hei2==m) l=lower_bound(ls2+1,ls2+tot2+1,Y[i].hei1)-ls2,r=tot2-1;
int xx=lower_bound(ls1+1,ls1+tot1+1,Y[i].xx)-ls1;
query(rt[l-1],rt[r],xx,1,tot1);
ans+=tmp,tmp=0;
}
printf("%lld\n",ans+1);
}
int main(){
mp['L']=1;mp['R']=2;mp['U']=3;mp['D']=4;
int T;cin>>T;
while(T--) solve();
}


## Rikka with Game

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)

Problem Description

Though both Rikka and Yuta are busy with study, on their common leisure, they always spend time with each other and sometimes play some interesting games.

Today, the rule of the game is quite simple. Given a string s with only lowercase letters. Rikka and Yuta need to operate the string in turns while the first operation is taken by Rikka.

In each turn, the player has two choices: The first one is to terminate the game, and the second one is to select an index i of s and right shift the value of char si, i.e., a→b,b→c,…,y→z,z→a.

If the game is still alive after 2101 turns, i.e., after Yuta finishes his 2100 turns, the game will end automatically. The final result is the value of s when the game is over.

Now, Rikka wants to minimize the lexicographical order of the result while Yuta wants to maximize it. You are required to calculate the result of the game if both Rikka and Yuta play optimally.

For two string a and b with equal length m, a is lexicographically smaller than b if and only if there exists an index i∈[1,n] which satisfies ai<bi and aj=bj holds for all j∈[1,i).
InputThe first line of the input contains an integer T(1≤T≤100), the number of test cases.

For each test case, the input contains a single line with a single string with only lowercase letters, the initial value of s(1≤|s|≤100).
OutputFor each test case, output a single line with a single string, the answer.

Sample Input

2
a
zbc

Sample Output

a
bbc

#### 签到题，只需要判断一下y和z的情况

#include <bits/stdc++.h>
using namespace std;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand()%x;}
char s[150];
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%s",s);
int l=strlen(s);
int pt=-1;
for(int i=0;i<l;i++){
if(s[i]=='y'){
pt=i;
}
else{
break;
}
}
pt+=1;
if(pt==l || s[pt]!='z'){
printf("%s\n",s);
}
else{
s[pt]='b';
printf("%s\n",s);
}
}
return 0;
}


## Rikka with Coin

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)

Problem Description

Rikka hates coins, and she used to never carry any coins with her. These days, Rikka is doing her summer internship abroad. Without mobile payment, Rikka has to face strange prices of commodities, and as a result of always using paper currency, she has to face mountainous coins on here table.

In the local currency system, there are 4 kinds of coins: 10 cents, 20 cents, 50 cents and 1 dollar. Up to now, Rikka has gained at least 10100 coins for each kind.

Now, Rikka is going to have dinner in the canteen, and she decides to pay the bill only with coins. There are n different combos in the canteen and the price of the ith is wi cents. Rikka would like to choose one combo as dinner but she has not decided to choose which one yet. Therefore, she wants to take some coins so that whichever she chooses, she can always pay the bill without receiving any change.

Since Rikka hates coins, she wants to carry as few coins as possible with her. As it is generally known that Rikka is not good at math, she wants you to help her make the decision.
InputThe first line of the input contains a single integer T(1≤T≤500), the number of test cases.

For each test case, the first line contains a single integer n(1≤n≤100), the number of combos sold in the canteen.

The second line contains n positive integers w1,…,wn(1≤wi≤109), which represents the prices.
OutputFor each test case, output a single line with a single integer which represents the minimum number of coins. If there is no valid solution, output −1.

HintIn the first test case, one optimal solution is to bring one coin of 10 cents and two coins of 20 cents.

In the second test case, one optimal solution is to bring 5 coins of one dollar.

Sample Input

3
5
10 20 30 40 50
5
100 200 300 400 500
1
1

Sample Output

3
5
-1

#### 签到题，注意特判40，60的情况就可以了，其他的就是什么大凑什么

#include <bits/stdc++.h>
using namespace std;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand()%x;}
typedef long long ll;
ll a[150];
ll b[150];
int ju(int a,int b,int c,int n){
while(c>0 && n-50>=0) n-=50,c-=1;
while(b>0 && n-20>=0) n-=20,b-=1;
while(a>0 && n-10>=0) n-=10,a-=1;
return n==0;
}
int main(){
int T,p;
scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
ll ma=-1;
int ffg=1;
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
b[i]=a[i]%100;
if(a[i]%10) ffg=0;
ma=max(ma,a[i]);
}
if(!ffg){
printf("-1\n");
continue;
}
int cnt=10,x,y,z;ll ans=1e16;
for(int i=0;i<=3;i++){
for(int j=0;j<=3;j++){
for(int k=0;k<=1;k++){
int fg=1;
for(int pt=1;pt<=n;pt++){
if(!ju(i,j,k,b[pt])){
fg=0;
break;
}
}
if(fg){
long long tmp=i+j+k;
if(tmp<cnt) cnt=tmp;
if(ma%100==0 && cnt==4){
ans=min(ans,1ll*3+1ll*ma/100);
}
else{
ans=min(ans,tmp+ma/100);
}
}
}
}
}

p=1;long long tmp=0;
for (int i=1;i<=n;i++)
if (a[i]==10||b[i]==30||b[i]==80) p=0;
else
{
if (b[i]==10) tmp=max(tmp,a[i]/100-1); else tmp=max(tmp,a[i]/100);
}
if (p) ans=min(ans,tmp+4);

if(cnt==10){
printf("-1\n");
}
else{
printf("%lld\n",ans);
}
}
return 0;
}


0 评论