例4-2 UVa489 Hangman Judge
模拟即可。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
char b1[27]={0},n1[100005],n2[100005];
int n=-1,solve(),res,lim1,i;
int solve(){
int chance=6,all=0;
lim1=strlen(n1);
for(i=0;i<lim1;i++){
if(!b1[n1[i]-'a']){
b1[n1[i]-'a']++;all++;
}
}
lim1=strlen(n2);
for(i=0;i<lim1;i++){
if(b1[n2[i]-'a']){
b1[n2[i]-'a']--;all--;
if(all==0&&(chance>=0))return 1;
}
else chance--;
}
if(chance<0)return -1;
if(all>0)return 0;
}
int main(){
for(scanf("%d",&n);n!=-1;n=-1,scanf("%d",&n)){
scanf("%s%s",n1,n2);
res=solve();
printf("Round %d\n",n);
if(res==1)printf("You win.\n");
if(res==0)printf("You chickened out.\n");
if(res==-1)printf("You lose.\n");
memset(b1,0,sizeof(b1));
}
return 0;
}
例4-3 UVa133 The Dole Queue
按照题意模拟即可。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
int p[25], n, k, m;
int main(){
for(n = 0,scanf("%d%d%d", &n, &k, &m); n != 0; n = 0,scanf("%d%d%d", &n, &k, &m)){
for(int i = 1; i <= n; ++i)
p[i] = i;
for(int l = 0, tmp = n, r = n + 1; tmp; ){
int s = k % tmp;
if(!s)s = tmp;
for(; s; ){
++l;
if(l > n)l = 1;
if(p[l])s--;
}
s = m % tmp;
if(!s)s = tmp;
for(; s; ){
--r;
if(r < 1)r = n;
if(p[r])s--;
}
if(l != r)
printf("%3d%3d", p[l], p[r]), tmp -= 2;
else
printf("%3d", p[l]), tmp--;
p[l] = p[r] = 0;
if(tmp)putchar(',');
}
putchar('\n');
}
return 0;
}
4-1 UVa1589 Xiangqi
长的模拟
注意当开始就将帅碰头的时候，不能认为黑方必胜。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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
using namespace std;
typedef long long ll;
int read(){
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
int n,bx,by,loc[10][3],puz[15][15];//g 0 c 1 h 2 r 3
int dx[]={-1,0,0,1},dy[]={0,1,-1,0};
int ddx[]={-2,-2,-1,1,-1,1,2,2},ddy[]={-1,1,2,2,-2,-2,-1,1};
bool ask(int cx,int cy){
for(int i=0;i<n;i++){
int kx=loc[i][1],ky=loc[i][2];
if(kx==cx&&cy==ky)continue;
if(loc[i][0]==0){
int flag=1;
if(cy!=ky)continue;
for(int j=cx+1;j<kx;j++)
if(puz[j][cy]){
flag=0;break;
}
if(flag)return true;
}else if(loc[i][0]==1){
int cnt=0;
if(cx==kx){
for(int j=min(cy,ky)+1;j<max(cy,ky);j++)
if(puz[cx][j])cnt++;
}else if(cy==ky){
for(int j=min(cx,kx)+1;j<max(cx,kx);j++)
if(puz[j][cy])cnt++;
}
if(cnt==1)return true;
}else if(loc[i][0]==2){
for(int j=0;j<8;j++){
int ccx=kx+ddx[j],ccy=ky+ddy[j];
if(ccx==cx&&ccy==cy&&!puz[kx+dx[j>>1]][ky+dy[j>>1]])
return true;
}
}else{
int flag=1;
if(cx==kx){
for(int j=min(cy,ky)+1;j<max(cy,ky);j++)
if(puz[cx][j]){
flag=0;break;
}
}else if(cy==ky){
for(int j=min(cx,kx)+1;j<max(cx,kx);j++)
if(puz[j][cy]){
flag=0;break;
}
}else flag=0;
if(flag)return true;
}
}
return false;
}
void init(){
memset(puz,0,sizeof(puz));
bx=read(),by=read();
char s[3];
for(int i=0;i<n;i++){
scanf("%s%d%d",s,&loc[i][1],&loc[i][2]);
if(s[0]=='G')loc[i][0]=0;
if(s[0]=='C')loc[i][0]=1;
if(s[0]=='H')loc[i][0]=2;
if(s[0]=='R')loc[i][0]=3;
puz[loc[i][1]][loc[i][2]]=1;
}
}
void solve(){
int ans=1;
for(int i=0;i<4;i++){
int cx=bx+dx[i],cy=by+dy[i];
if(!cx||cx>3||cy<4||cy>6)continue;
puz[cx][cy]=1;
if(!ask(cx,cy)){
ans=0;break;
}
puz[cx][cy]=0;
}
if(!ans)printf("NO\n");
else printf("YES\n");
}
int main(){
while(n=read()){
init();
solve();
}
return 0;
}
4-4 UVa253 Cube painting
让第一个骰子不断向左/向上翻转，直到所有视图均被翻出位置。若此时所有翻出的可能的视图中没有第二个骰子的视图则认为两个骰子不等价。反之等价。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
49
using namespace std;
typedef long long ll;
int read(){
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
bool vis[1000];
char s[15];
int h2,k1[]={4,0,2,3,5,1},k2[]={0,2,4,1,3,5};
int cg(char c){
if(c=='r')return 0;
if(c=='g')return 1;
if(c=='b')return 2;
}
void dfs(int hs){
int bs[7],hh1=0,hh2=0;
for(int i=5;i>=0;i--)bs[i]=hs%3,hs/=3;
for(int i=0;i<6;i++)hh1=hh1*3+bs[k1[i]];
for(int i=0;i<6;i++)hh2=hh2*3+bs[k2[i]];
if(!vis[hh1])vis[hh1]=1,dfs(hh1);
if(!vis[hh2])vis[hh2]=1,dfs(hh2);
}
void init(){
memset(vis,0,sizeof(vis));
int h1=0;h2=0;
for(int i=0;i<6;i++)h1=h1*3+cg(s[i]);
for(int i=6;i<12;i++)h2=h2*3+cg(s[i]);
vis[h1]=1;
dfs(h1);
}
void solve(){
if(vis[h2])printf("TRUE\n");
else printf("FALSE\n");
}
int main(){
while(scanf("%s",s)==1){
init();
solve();
}
return 0;
}
4-5 UVa1590 IP Networks
模拟即可
熟悉位运算的好题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
49
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
typedef unsigned int u_int;
u_int ip[1005] = {0};
int m;
void init(){
memset(ip, 0, sizeof(ip));
for(int i = 0; i < m; ++i)
for(int j = 3; j >= 0; --j){
u_int t = read();
ip[i] += (t << (j * 8));
}
}
void solve(){
int n = 0, i;
for(; n <= 31; ++n){
u_int pp = ~((1 << n) - 1);
for(i = 1; i < m; ++i)
if((pp & ip[i]) != (pp & ip[i - 1]))break ;
if(i == m)break ;
}
u_int ans = ~((1 << n) - 1), t = 0xff000000;
ip[0] &= ans;
for(int j = 3; j >= 0; --j)
printf("%u%s", (ip[0] & t) >> (j * 8), j ? "." : "\n"), t >>= 8;
t = 0xff000000;
for(int j = 3; j >= 0; --j)
printf("%u%s", (ans & t) >> (j * 8), j ? "." : "\n"), t >>= 8;
}
int main(){
while(scanf("%d", &m) == 1){
init();
solve();
}
return 0;
}
4-7 UVa509 RAID!
模拟…即可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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int d, s, b, val, seq[100005];
char data[7][6500];
void init(){
char ord[3];
s = read(), b = read();
scanf("%s", ord);
val = (ord[0] == 'E' ? 0 : 1);
for(int i = 0; i < d; ++i)
scanf("%s", data[i]);
}
void solve(){
int cur = 0, tot = 0;
for(int i = 0; i < b; ++i){
for(int j = 0; j < s; ++j){
//当前的校验块在磁盘号为cur
int c = 0, cnt = 0, id;
for(int k = 0; k < d; ++k){
if(data[k][i * s + j] == 'x')
cnt++, id = k;//坏的在id处
else
c ^= (data[k][i * s + j] - '0');
}
if(cnt >= 2)
goto failed;
else if(cnt == 1)
data[id][i * s + j] = (c ^ val) + '0';
else{
if(c != val)//校验错误
goto failed;
}
}
for(int j = 0; j < d; ++j){
if(j == cur)continue ;
for(int k = 0; k < s; ++k){
if(data[j][i * s + k] - '0')
seq[tot >> 2] += (1 << (3 - (tot % 4)));
tot++;
}
}
cur = (cur + 1) % d;
}
printf("valid, contents are: ");
while(tot % 4)tot++;
tot >>= 2;
for(int i = 0; i < tot; ++i){
if(seq[i] < 10)printf("%d", seq[i]);
else putchar(seq[i] - 10 + 'A');
}
printf("\n");
return ;
failed:
printf("invalid.\n");
}
int main(){
for(int T = 1; ; ++T){
d = read();
if(!d)break ;
printf("Disk set %d is ", T);
init();
solve();
memset(seq, 0, sizeof(seq));
}
return 0;
}
4-9 Uva1591 Data Mining（待补充）
4-10 UVa815 Flooded!
先对高度排一个序，然后从最下方向上面淹即可。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
49
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int n, m;
double h[905], V;
void init(){
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
h[i * m + j] = read();
V = read(), V /= 100.0;
sort(h, h + n * m);
h[n * m] = 100000000;
}
void solve(){
double tot = 0.0, ans1, ans2;
int i;
for(i = 1; i <= n * m; ++i){
tot += h[i - 1];
if(V < i * h[i] - tot)
break;
}
ans1 = (V + tot) / (double)i,
ans2 = 100.0 * i / (n * m);
printf("Water level is %.2lf meters.\n%.2lf percent of the region is under water.\n\n", ans1, ans2);
}
int main(){
for(int T = 1; ; ++T){
n = read(), m = read();
if(!n && !m)break ;
printf("Region %d\n", T);
init();
solve();
}
return 0;
}