ACM | 落絮飞雁的个人网站

Problem Description

Once there was a special graph. This graph had n vertices and some edges. Each edge was either white or black. There was no edge connecting one vertex and the vertex itself. There was no two edges connecting the same pair of vertices. It is special because the each vertex is connected to at most two black edges and at most two white edges.

One day, the demon broke this graph by copying all the vertices and in one copy of the graph, the demon only keeps all the black edges, and in the other copy of the graph, the demon keeps all the white edges. Now people only knows there are w0 vertices which are connected with no white edges, w1 vertices which are connected with 1 white edges, w2 vertices which are connected with 2 white edges, b0 vertices which are connected with no black edges, b1 vertices which are connected with 1 black edges and b2 vertices which are connected with 2 black edges.

The precious graph should be fixed to guide people, so some people started to fix it. If multiple initial states satisfy the restriction described above, print any of them.

Input

The first line of the input is a single integer T (T≤700), indicating the number of testcases.

Each of the following T lines contains w0,w1,w2,b0,b1,b2. It is guaranteed that 1≤w0,w1,w2,b0,b1,b2≤2000 and b0+b1+b2=w0+w1+w2.

It is also guaranteed that the sum of all the numbers in the input file is less than 300000.

Output

For each testcase, if there is no available solution, print −1. Otherwise, print m in the first line, indicating the total number of edges. Each of the next m lines contains three integers x,y,t, which means there is an edge colored t connecting vertices x and y. t=0 means this edge white, and t=1 means this edge is black. Please be aware that this graph has no self-loop and no multiple edges. Please make sure that 1≤x,y≤b0+b1+b2.

Sample Input

2
1 1 1 1 1 1
1 2 2 1 2 2

Sample Output

-1
6
1 5 0
4 5 0
2 4 0
1 4 1
1 3 1
2 3 1

题目大意是构造一个无向图。先考虑白色边，构造常链连接1和2即可。注意排重。

参考代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
#define sf scanf
int T;
int a[5],b[5];
int d[1000005];
int main()
{
    sf("%d",&T);
    while(T--)
    {
        for(int i = 0;i<3;i++)sf("%d",a+i);
        for(int i = 0;i<3;i++)sf("%d",b+i);
        int sum = 0;
        for(int i = 0;i<3;i++)sum+=a[i];
        if( (a[1]&1) || (b[1]&1) )
        {
            puts("-1");
            continue;
        }
        if(sum==4)
        {
            puts("4\n1 2 0\n1 3 0\n2 3 1\n3 4 1");
            continue;
        }
        printf("%d\n",a[1]/2+a[2]+b[1]/2+b[2]);
        int t = 1;
        while(a[2]!=-1){printf("%d %d 0\n",t,t+1);t++;a[2]--;}t++;
        while(a[1]!=2){printf("%d %d 0\n",t,t+1);t+=2;a[1]-=2;}
 
            int tt = 0;
            for(int i = 1;i<=sum;i+=2) d[tt++] = i;
            for(int i = 2;i<=sum;i+=2)d[tt++] = i;
 
        t = 0;
        while(b[2]!=-1){printf("%d %d 1\n",min(d[t],d[t+1]),max(d[t],d[t+1]));t++;b[2]--;}t++;
        while(b[1]!=2){printf("%d %d 1\n",min(d[t],d[t+1]),max(d[t],d[t+1]));t+=2;b[1]-=2;}
 
    }
}

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

using namespace std;

#define sf scanf

int T;

int a[5],b[5];

int d[1000005];

int main()

{

sf("%d",&T);

while(T--)

{

for(int i = 0;i<3;i++)sf("%d",a+i);

for(int i = 0;i<3;i++)sf("%d",b+i);

int sum = 0;

for(int i = 0;i<3;i++)sum+=a[i];

if( (a[1]&1) || (b[1]&1) )

{

puts("-1");

continue;

}

if(sum==4)

{

puts("4\n1 2 0\n1 3 0\n2 3 1\n3 4 1");

continue;

}

printf("%d\n",a[1]/2+a[2]+b[1]/2+b[2]);

int t = 1;

while(a[2]!=-1){printf("%d %d 0\n",t,t+1);t++;a[2]--;}t++;

while(a[1]!=2){printf("%d %d 0\n",t,t+1);t+=2;a[1]-=2;}

int tt = 0;

for(int i = 1;i<=sum;i+=2) d[tt++] = i;

for(int i = 2;i<=sum;i+=2)d[tt++] = i;

t = 0;

while(b[2]!=-1){printf("%d %d 1\n",min(d[t],d[t+1]),max(d[t],d[t+1]));t++;b[2]--;}t++;

while(b[1]!=2){printf("%d %d 1\n",min(d[t],d[t+1]),max(d[t],d[t+1]));t+=2;b[1]-=2;}

}

HDOJ1085:Holding Bin-Laden Captive!——母函数

Problem Description
We all know that Bin-Laden is a notorious terrorist, and he has disappeared for a long time. But recently, it is reported that he hides in Hang Zhou of China!
“Oh, God! How terrible! ”

Don’t be so afraid, guys. Although he hides in a cave of Hang Zhou, he dares not to go out. Laden is so bored recent years that he fling himself into some math problems, and he said that if anyone can solve his problem, he will give himself up!
Ha-ha! Obviously, Laden is too proud of his intelligence! But, what is his problem?
“Given some Chinese Coins (硬币) (three kinds– 1, 2, 5), and their number is num_1, num_2 and num_5 respectively, please output the minimum value that you cannot pay with given coins.”
You, super ACMer, should solve the problem easily, and don’t forget to take $25000000 from Bush!

Input
Input contains multiple test cases. Each test case contains 3 positive integers num_1, num_2 and num_5 (0<=num_i<=1000). A test case containing 0 0 0 terminates the input and this test case is not to be processed.

Output
Output the minimum positive value that one cannot pay with given coins, one line for one case.

Sample Input
1 1 3
0 0 0

Sample Output
4

参考代码：

#include<cstdio>
#include<cstring>
#include<cmath>
int c1[1000],c2[10000];
int main()
{
	int n1,n2,n5;
	while(scanf("%d%d%d",&n1,&n2,&n5)==3,n1+n2+n5)
	{
		int n,i,j,k;
		n=n1+n2*2+n5*5;
		for(i=0;i<=n;i++)//init c1 c2
		{
			c1[i]=0;c2[i]=0;
		}
		for(i=0;i<=n1;i++)//只有 1
		{
			c1[i]=1;
		}
		for(i=0;i<=n1;i++)//存在1和2
		{
			for(j=0;j<=n2*2;j+=2)
			{
				c2[i+j]+=c1[i];
			}
		}
		for(k=0;k<=n1+n2*2;k++)
		{
			c1[k]=c2[k];c2[k]=0;
		}
		for(j=0;j<=n1+n2*2;j++)//存在1、2、5
		{
			for(k=0;k<=n5*5;k+=5)
			{
				c2[k+j]+=c1[j];
			}
		}
		for(i=0;i<=5*n5+2*n2+n1;i++)
		{
			c1[i]=c2[i];c2[i]=0;
		}
		bool flag=0;
		for(i=0;i<=n;i++)
		{
			if(c1[i]==0)
			{
				printf("%d\n",i);
				flag=1;
				break;
			}
		}
			if(!flag)
				printf("%d\n",n+1);
		}
		return 0;
	}

#include<cstdio>

#include<cstring>

#include<cmath>

int c1[1000],c2[10000];

int main()

{

int n1,n2,n5;

while(scanf("%d%d%d",&n1,&n2,&n5)==3,n1+n2+n5)

{

int n,i,j,k;

n=n1+n2*2+n5*5;

for(i=0;i<=n;i++)//init c1 c2

{

c1[i]=0;c2[i]=0;

}

for(i=0;i<=n1;i++)//只有 1

{

c1[i]=1;

}

for(i=0;i<=n1;i++)//存在1和2

{

for(j=0;j<=n2*2;j+=2)

{

c2[i+j]+=c1[i];

}

for(k=0;k<=n1+n2*2;k++)

{

c1[k]=c2[k];c2[k]=0;

}

for(j=0;j<=n1+n2*2;j++)//存在1、2、5

{

for(k=0;k<=n5*5;k+=5)

{

c2[k+j]+=c1[j];

}

for(i=0;i<=5*n5+2*n2+n1;i++)

{

c1[i]=c2[i];c2[i]=0;

}

bool flag=0;

for(i=0;i<=n;i++)

{

if(c1[i]==0)

{

printf("%d\n",i);

flag=1;

break;

}

if(!flag)

printf("%d\n",n+1);

}

return 0;

}

HDOJ1038:Biker’s Trip Odometer——数学题

Problem Description
Most bicycle speedometers work by using a Hall Effect sensor fastened to the front fork of the bicycle. A magnet is attached to one of the spokes on the front wheel so that it will line up with the Hall Effect switch once per revolution of the wheel. The speedometer monitors the sensor to count wheel revolutions. If the diameter of the wheel is known, the distance traveled can be easily be calculated if you know how many revolutions the wheel has made. In addition, if the time it takes to complete the revolutions is known, the average speed can also be calculated.
For this problem, you will write a program to determine the total distance traveled (in miles) and the average speed (in Miles Per Hour) given the wheel diameter, the number of revolutions and the total time of the trip. You can assume that the front wheel never leaves the ground, and there is no slipping or skidding.

Input
Input consists of multiple datasets, one per line, of the form:

diameter revolutions time

The diameter is expressed in inches as a floating point value. The revolutions is an integer value. The time is expressed in seconds as a floating point value. Input ends when the value of revolutions is 0 (zero).

Output
For each data set, print:

Trip #N: distance MPH

Of course N should be replaced by the data set number, distance by the total distance in miles (accurate to 2 decimal places) and MPH by the speed in miles per hour (accurate to 2 decimal places). Your program should not generate any output for the ending case when revolutions is 0.

Constants

For p use the value: 3.1415927.
There are 5280 feet in a mile.
There are 12 inches in a foot.
There are 60 minutes in an hour.
There are 60 seconds in a minute.
There are 201.168 meters in a furlong.

Sample Input
26 1000 5
27.25 873234 3000
26 0 1000

Sample Output
Trip #1: 1.29 928.20
Trip #2: 1179.86 1415.84

一道数学题。简单水过。注意格式即可。
代码：

#include<stdio.h>
#define Pi 3.1415927

int main()
{
	int n,c=0;
	double t,d,v,s;
	while(scanf("%lf%d%lf",&d,&n,&t)!=EOF && n!=0)
	{
		s=n*Pi*d/12/5280;
		v=s/(t/60/60);
		printf("Trip #%d: %.2lf %.2lf\n",++c,s,v);
	}
		return 0;
}

#include<stdio.h>

#define Pi 3.1415927

int main()

{

int n,c=0;

double t,d,v,s;

while(scanf("%lf%d%lf",&d,&n,&t)!=EOF && n!=0)

{

s=n*Pi*d/12/5280;

v=s/(t/60/60);

printf("Trip #%d: %.2lf %.2lf\n",++c,s,v);

}

return 0;

}

POJ3279:Fliptile——搜索、开关问题

约翰又来折腾牛了……
继续阅读POJ3279:Fliptile——搜索、开关问题

POJ3276：Face The Right Way——开关问题、简单DP

~~牛头人~~约翰和牛的故事。
继续阅读POJ3276：Face The Right Way——开关问题、简单DP

HDOJ1733：Escape——网络流分层图

该来的总是会来的，写一道最头痛的网络流问题。
继续阅读HDOJ1733：Escape——网络流分层图

HDOJ2127:Polish notation——表达式转换

Problem Description
Reverse Polish notation (RPN) is a method for representing expressions in which the operator symbol is placed after the arguments being operated on.
Polish notation, in which the operator comes before the operands, was invented in the 1920s by the Polish mathematician Jan Lucasiewicz.
In the late 1950s, Australian philosopher and computer scientist Charles L. Hamblin suggested placing the operator after the operands and hence created reverse polish notation.

RPN has the property that brackets are not required to represent the order of evaluation or grouping of the terms.
RPN expressions are simply evaluated from left to right and this greatly simplifies the computation of the expression within computer programs.
As an example, the arithmetic expression (3+4)*5 can be expressed in RPN as 3 4 + 5 *.

Reverse Polish notation, also known as postfix notation, contrasts with the infix notation of standard arithmetic expressions in which the operator symbol appears between the operands. So Polish notation just as prefix notation.

Now, give you a string of standard arithmetic expressions, please tell me the Polish notation and the value of expressions.

Input
There’re have multi-case. Every case put in one line, the expressions just contain some positive integers(all less than 100, the number of integers less than 20), bi-operand operators(only have 3 kinds : +,-,*) and some brackets'(‘,’)’.
you can assume the expressions was valid.

Output
Each case output the Polish notation in first line, and the result of expressions was output in second line.
all of the answers are no any spaces and blank line.the answer will be not exceed the 64-signed integer.

Sample Input
1+2-3*(4-5)
1+2*(3-4)-5*6

Sample Output
Case 1:
– + 1 2 * 3 – 4 5
6
Case 2:
– + 1 * 2 – 3 4 * 5 6
-31

题目考察表达式的转换将中缀表达式转换成前置表达式（波兰式），并计算出结果。可以直接套模板……需要注意表达式中空格的位置；字符串需要用__int64存贮。

关于前置表达式和后置表达式的转换方法可以参考这篇博文：波兰式、逆波兰式与表达式求值

参考代码：

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

char stack[500];                    
int top;                        //栈顶指针       
char output[500], input[500];        
int outLen;

int priority(char op)           //定义运算符优先级     
{
    if (op=='+' || op=='-')
        return 1;
    if (op=='*' || op=='/')
        return 2;
    else
        return 0;
}

bool isOperator(char op)                
{
    return (op=='+' || op=='-' || op=='*' || op=='/');
}

void Polish(char *s,int len)            
{
    memset(output,'\0',sizeof output);    
    outLen = 0;
    for (int i=len-1; i >= 0; --i)        
    {
        if (isdigit(s[i]))                
        {
            output[outLen++] = s[i];    
            while (i-1 >= 0 && isdigit(s[i-1]))
            {
                output[outLen++] = s[i-1];
                --i;
            }
            output[outLen++] = ' ';        
        }
        if (s[i]==')')                    
        {
            ++top;
            stack[top] = s[i];
        }
        while (isOperator(s[i]))        
        {                                                
            if (top==0 || stack[top]==')' || priority(s[i]) >= priority(stack[top])) 
            {
                ++top;
                stack[top] = s[i];
                break;
            }
            else
            {
                output[outLen++] = stack[top];
                output[outLen++] = ' ';
                --top;
            }
        }
        if (s[i]=='(')                    
        {
            while (stack[top]!=')')
            {
                output[outLen++] = stack[top];
                output[outLen++] = ' ';
                --top;
            }
            --top;    
        }
    }
    while (top!=0)                        
    {
        output[outLen++] = stack[top];
        output[outLen++] = ' ';
        --top;
    }
}

char DstBuf[200];
char* OP(char* op1,char* op2,char op)
{
    __int64 res = 0;
    if (op=='+')
        res = _atoi64(op1) + _atoi64(op2);
    else if (op=='-')
        res = _atoi64(op1) - _atoi64(op2);
    else if (op=='*')
        res = _atoi64(op1) * _atoi64(op2);
    else if (op=='/')
        res = _atoi64(op1) / _atoi64(op2);
    _i64toa(res,DstBuf,10);
    return DstBuf;
}

char cSt1[200][80], cSt2[200][80];
__int64 calc(char *s)                
{
    int top1=0, top2=0, i;
    for (i=0; s[i]; ++i)
    {
        if (s[i] && s[i] != ' ')
        {
            ++top1;
            sscanf(s+i,"%s",cSt1[top1]);        
            while (s[i] && s[i] != ' ')
                ++i;
        }
    }
    while (top1 != 0)    
    {
        if (!isdigit(cSt1[top1][0]))    
        {
            OP(cSt2[top2], cSt2[top2-1], cSt1[top1][0]);
            memcpy(cSt2[top2-1],DstBuf,sizeof DstBuf);
            --top2;                    
            --top1;                        
        }
        else
        {
            ++top2;                        
            memcpy(cSt2[top2],cSt1[top1],sizeof cSt1[top1]);
            --top1;                        
        }
    }
    return _atoi64(cSt2[1]);
}
int main()
{
    int T = 1;
    while (gets(input))
    {
        Polish(input, strlen(input));
        reverse(output,output+outLen-1);
        output[outLen-1] = '\0';
        printf("Case %d:\n%s\n",T++,output);
        printf("%I64d\n",calc(output));//注意要__int64
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

#include <iostream>

#include <string>

#include <algorithm>

using namespace std;

char stack[500];

int top; //栈顶指针

char output[500], input[500];

int outLen;

int priority(char op) //定义运算符优先级

{

if (op=='+' || op=='-')

return 1;

if (op=='*' || op=='/')

return 2;

else

return 0;

}

bool isOperator(char op)

{

return (op=='+' || op=='-' || op=='*' || op=='/');

}

void Polish(char *s,int len)

{

memset(output,'\0',sizeof output);

outLen = 0;

for (int i=len-1; i >= 0; --i)

{

if (isdigit(s[i]))

{

output[outLen++] = s[i];

while (i-1 >= 0 && isdigit(s[i-1]))

{

output[outLen++] = s[i-1];

--i;

}

output[outLen++] = ' ';

}

if (s[i]==')')

{

++top;

stack[top] = s[i];

}

while (isOperator(s[i]))

{

if (top==0 || stack[top]==')' || priority(s[i]) >= priority(stack[top]))

{

++top;

stack[top] = s[i];

break;

}

else

{

output[outLen++] = stack[top];

output[outLen++] = ' ';

--top;

}

if (s[i]=='(')

{

while (stack[top]!=')')

{

output[outLen++] = stack[top];

output[outLen++] = ' ';

--top;

}

--top;

}

while (top!=0)

{

output[outLen++] = stack[top];

output[outLen++] = ' ';

--top;

}

char DstBuf[200];

char* OP(char* op1,char* op2,char op)

{

__int64 res = 0;

if (op=='+')

res = _atoi64(op1) + _atoi64(op2);

else if (op=='-')

res = _atoi64(op1) - _atoi64(op2);

else if (op=='*')

res = _atoi64(op1) * _atoi64(op2);

else if (op=='/')

res = _atoi64(op1) / _atoi64(op2);

_i64toa(res,DstBuf,10);

return DstBuf;

}

char cSt1[200][80], cSt2[200][80];

__int64 calc(char *s)

{

int top1=0, top2=0, i;

for (i=0; s[i]; ++i)

{

if (s[i] && s[i] != ' ')

{

++top1;

sscanf(s+i,"%s",cSt1[top1]);

while (s[i] && s[i] != ' ')

++i;

}

while (top1 != 0)

{

if (!isdigit(cSt1[top1][0]))

{

OP(cSt2[top2], cSt2[top2-1], cSt1[top1][0]);

memcpy(cSt2[top2-1],DstBuf,sizeof DstBuf);

--top2;

--top1;

}

else

{

++top2;

memcpy(cSt2[top2],cSt1[top1],sizeof cSt1[top1]);

--top1;

}

return _atoi64(cSt2[1]);

}

int main()

{

int T = 1;

while (gets(input))

{

Polish(input, strlen(input));

reverse(output,output+outLen-1);

output[outLen-1] = '\0';

printf("Case %d:\n%s\n",T++,output);

printf("%I64d\n",calc(output));//注意要__int64

}

return 0;

}

HDOJ1042:N!–大数

Problem Description
Given an integer N(0 ≤ N ≤ 10000), your task is to calculate N!

Input
One N in one line, process to the end of file.

Output
For each N, output N! in one line.

Sample Input
1
2
3

Sample Output
1
2
6

要求计算10000以内的阶乘,典型的大数问题.这里用的是五位一存的方法. 关于X位一存的解释可以看这篇文章. 注意特殊情况(0,1)下的处理.

#include <stdio.h>
#include <string.h>
#define MOD 100000
int main()
{
    int a[8000];    
    int i,k,n,t,la;
    while(~scanf("%d",&n))
    {
        if(n==0||n==1) {printf("1\n");continue;}

        a[0] = 1; 
        la = 1;
        t = 0;
        for(k=2; k<=n; k++)
        {
            for(i=0; i<la; i++)
            {
                t += k * a[i];
                a[i] = t%MOD;
                t = t/MOD;
            }
            if (t > 0)   
            {    
                a[la++] = t;
                t = 0; 
            } 
        }
        printf("%d",a[la-1]);
        for(i=la-2; i>=0; i--)
            printf("%05d",a[i]);
        printf("\n");
    }
    return 0;
}

#include <stdio.h>

#include <string.h>

#define MOD 100000

int main()

{

int a[8000];

int i,k,n,t,la;

while(~scanf("%d",&n))

{

if(n==0||n==1) {printf("1\n");continue;}

a[0] = 1;

la = 1;

t = 0;

for(k=2; k<=n; k++)

{

for(i=0; i<la; i++)

{

t += k * a[i];

a[i] = t%MOD;

t = t/MOD;

}

if (t > 0)

{

a[la++] = t;

t = 0;

}

printf("%d",a[la-1]);

for(i=la-2; i>=0; i--)

printf("%05d",a[i]);

printf("\n");

}

return 0;

}

分类：ACM

HDOJ1015：Safecracker

HDOJ1014：Uniform Generator

HDOJ5302：Connect the Graph——无向图构造

Problem Description

Input

Output

Sample Input

Sample Output

参考代码：

HDOJ1085:Holding Bin-Laden Captive!——母函数

HDOJ1038:Biker’s Trip Odometer——数学题

POJ3279:Fliptile——搜索、开关问题

POJ3276：Face The Right Way——开关问题、简单DP

HDOJ1733：Escape——网络流分层图

HDOJ2127:Polish notation——表达式转换

HDOJ1042:N!–大数