http://acm.buaa.edu.cn/contest/63/home/
=A+B problem
签到题，输入A，B，输出A+B
Code：
C & C++
#include<stdio.h>
int main()
{
int a,b,n,i;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d %d",&a,&b);
printf("%d\n",a+b);}
return 0;
}
python:
count = int(raw_input())
for i in range(count):
a, b = raw_input().split(' ')
print str(int(a)+int(b))
Pascal:
var n,i,a,b:longint; begin readln(n); for i:=1 to n do begin readln(a,b); writeln(a+b); end; end.
A 掷骰子
简单概率计算题。填入的数字肯定是0~总面数-1 。 因此排序贪心即可。
From AC：
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <ctime>
#include <cstdio>
#include <cstring>
using namespace std;
typedef double db;
const db EPS = 1e-6;
const db PI = acos(-1.0);
int sign(db x){return x < - EPS ? - 1 : x > EPS ; }
const int MAXN = 111 ;
int c[ MAXN ];
int main(){
int n;
while(cin>>n){
for(int i=0;i<n;++i) cin>>c[i];
sort(c,c+n);
int tot = -1;
for(int i=0;i<n;++i) tot += c[i];
//[1..tot]
db ans = 0.0;
for(int i = n-1;i>=0;--i){
db t = 1.0 / c[i], s=.0;
while( c[i] -- ) {
s += tot --;
}
ans += t * s ;
}
printf("%.2f\n", ans);
}
return 0;
}
B Taylor
数学计算证明题，直接输出2012即可。很多同学Wrong Answer的原因是在程序中计算，导致double精度误差从而答案变成2011。
证明如下（From BUAA_LJC）
由tan(a+b) = (tan(a)+tan(b))/(1-tan(a)*tan(b))得1/a = tan(arctan(1/b)+arctan(1/c)) = (1/b+1/c)/(1-1/b*1/c) = (b+c)/(cb-1)=>cb-1=ab+ac => b*c-a*b-c*a=1故ans = 2012/1 = 2012
int main(){
LL a, b;
int t;
cin >>t;
while(t--){
cin>>a>>b; cout << 2012<<endl;
}
return 0;
}
C 得了多少奖
乱搞题，辛苦了各位了。
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
typedef double db;
typedef long long LL;
const db EPS = 1e-6;
const db PI = acos(-1.0);
int sign(db x){return x < - EPS ? - 1 : x > EPS ; }
//2Au 5Ag 2Cu 0Fe
//map< string, map<string, int > > M ;
map< string, string> M ;
string tos(int x){
string w = "7";
w[0]='0'+x;
return w;
}
void pre(){
M["10061023"]="0Au 1Ag 2Cu 0Fe";
M["10061061"]="0Au 1Ag 2Cu 0Fe";
M["10061189"]="0Au 0Ag 2Cu 0Fe";
M["10061210"]="0Au 0Ag 1Cu 0Fe";
M["10091234"]="0Au 1Ag 3Cu 0Fe";
M["10131061"]="0Au 1Ag 0Cu 0Fe";
M["10131064"]="0Au 1Ag 0Cu 0Fe";
M["10211031"]="0Au 1Ag 3Cu 0Fe";
M["10211072"]="0Au 1Ag 3Cu 0Fe";
M["11061214"]="0Au 0Ag 2Cu 0Fe";
M["11061215"]="0Au 0Ag 2Cu 0Fe";
M["11211078"]="0Au 0Ag 2Cu 0Fe";
M["11211104"]="0Au 0Ag 2Cu 0Fe";
M["11211116"]="0Au 0Ag 2Cu 0Fe";
M["11211119"]="0Au 1Ag 0Cu 0Fe";
M["34060609"]="0Au 0Ag 1Cu 0Fe";
M["34060814"]="1Au 0Ag 0Cu 0Fe";
M["35060616"]="0Au 0Ag 2Cu 1Fe";
M["35060622"]="2Au 5Ag 2Cu 0Fe";
M["35060722"]="0Au 1Ag 2Cu 1Fe";
M["35090209"]="0Au 1Ag 0Cu 0Fe";
M["35211219"]="0Au 1Ag 1Cu 1Fe";
M["35211231"]="0Au 1Ag 1Cu 1Fe";
M["35211312"]="1Au 3Ag 0Cu 0Fe";
M["35211425"]="2Au 3Ag 2Cu 0Fe";
M["35230107"]="0Au 0Ag 2Cu 0Fe";
M["35230115"]="0Au 0Ag 1Cu 1Fe";
M["36030411"]="0Au 1Ag 3Cu 1Fe";
M["36060415"]="0Au 0Ag 1Cu 0Fe";
M["36060610"]="0Au 1Ag 2Cu 0Fe";
M["36090119"]="0Au 0Ag 2Cu 0Fe";
M["36091223"]="0Au 1Ag 2Cu 0Fe";
M["36093117"]="0Au 0Ag 1Cu 0Fe";
M["36211309"]="0Au 4Ag 2Cu 0Fe";
M["36211409"]="0Au 1Ag 2Cu 0Fe";
M["36211420"]="0Au 2Ag 1Cu 0Fe";
M["36230116"]="0Au 0Ag 1Cu 0Fe";
M["37060221"]="0Au 2Ag 1Cu 0Fe";
M["37071426"]="0Au 0Ag 0Cu 1Fe";
M["37211126"]="0Au 0Ag 0Cu 2Fe";
M["37211226"]="0Au 1Ag 0Cu 0Fe";
M["37211525"]="0Au 0Ag 0Cu 1Fe";
M["38022626"]="0Au 0Ag 0Cu 1Fe";
M["38211114"]="0Au 0Ag 0Cu 1Fe";
M["38211212"]="1Au 6Ag 0Cu 0Fe";
M["38211219"]="0Au 2Ag 0Cu 1Fe";
M["38211313"]="0Au 0Ag 0Cu 1Fe";
M["38211314"]="1Au 5Ag 0Cu 0Fe";
M["38211316"]="0Au 2Ag 0Cu 0Fe";
M["38211324"]="0Au 0Ag 1Cu 1Fe";
M["38211406"]="0Au 0Ag 1Cu 1Fe";
M["38211416"]="0Au 0Ag 1Cu 0Fe";
M["38211424"]="0Au 0Ag 1Cu 0Fe";
M["38211503"]="0Au 0Ag 1Cu 1Fe";
M["38211516"]="0Au 0Ag 1Cu 0Fe";
M["38230210"]="0Au 1Ag 0Cu 1Fe";
M["38230214"]="0Au 1Ag 0Cu 0Fe";
M["39055104"]="0Au 3Ag 1Cu 0Fe";
M["39061124"]="0Au 0Ag 1Cu 0Fe";
M["39061326"]="0Au 0Ag 1Cu 0Fe";
M["39061328"]="0Au 0Ag 1Cu 0Fe";
M["39061412"]="0Au 0Ag 1Cu 1Fe";
M["39061512"]="1Au 3Ag 1Cu 1Fe";
M["39211108"]="0Au 1Ag 0Cu 1Fe";
M["39211306"]="0Au 0Ag 0Cu 1Fe";
M["39211509"]="0Au 2Ag 1Cu 1Fe";
M["39231214"]="0Au 1Ag 0Cu 1Fe";
M["SY0906111"]="0Au 2Ag 0Cu 0Fe";
M["SY0906226"]="0Au 1Ag 1Cu 0Fe";
}
int main(){
pre();
/*freopen("in.txt","r", stdin);
freopen("out.txt","w", stdout);
string id[5], jp;
int cnt[5]={0,0,0,0};
while( cin >> id[0] >> id[1] >>id[2] ) {
cin >> jp;
string w ;
if( jp == "金奖") w = "Au", ++ cnt[0];
else if(jp == "银奖") w = "Ag", ++ cnt[1];
else if(jp == "铜奖") w= "Cu", ++ cnt[2];else w = "Fe", ++ cnt[3];
for(int i=0;i<3;++i) ++ M[ id[i] ][ w ] ;
}
for(int i=0;i<4;++i) cout << cnt[i] <<' '; cout << endl;
for( map< string, map<string, int > >::iterator p = M.begin(); p != M.end(); ++ p) {
string id = p -> first ;
string res = "";
res += tos( p->second[ "Au" ] ) + "Au ";
res += tos( p->second[ "Ag" ] ) + "Ag ";
res += tos( p->second[ "Cu" ] ) + "Cu ";
res += tos( p->second[ "Fe" ] ) + "Fe";
printf("M[\"%s\"]=\"%s\";\n", id.c_str(), res.c_str());
}*/
string id;
while( cin >> id) {
for(int i = 0; i < id.length(); ++ i) if( id[i] >= 'a' && id[i] <= 'z') id[i] -= 32;
cout << M[id] << endl;
}
return 0;
}
D GGCD
数学题。求GCD(A , B^B) 有两种方法：
1、因为B比较小，可以求B次GCD 然后相乘
2、将A、B分解质因数，B质因数个数 * B。然后遍历质因数，A、B质因数取小相乘即可。
3、算出b^b 对 a 的余数，和a做gcd
//bc-1 = a(b+c)
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <cstdio>
#include <algorithm>
#define N 25005
using namespace std;
int a , b;
int gcd(int x ,int y) {return y == 0 ? x : gcd(y , x % y);}
int main()
{
while (cin >> a >> b)
{
int x = 1;
for (int i = 1 ; i <= b ;i ++)
x *= b , x %= a;
cout << gcd(x , a) << endl;
}
return 0;
}
E Party
图论，二分图匹配。将男生看做一部分点，女生一部分点，建图。n^2的匈牙利算法即可，或者搜索。
#include <stdio.h>
#include <string.h>
int n1,n2,m,ans;
int result[530*2],s[530*2]; //记录V2中的点匹配的点的编号
bool state [530*2]; //记录V2中的每个点是否被搜索过
int data[530*2][530];//邻接矩阵 true代表有边相连
void init()
{
int t1,t2;
memset(data,0,sizeof(data));
memset(result,0,sizeof(result));
ans = 0;
for (int i = 1; i <= n1; i++)
{
scanf("%d",&s[i]);
for (int j = 1; j <= s[i]; j++)
{
scanf("%d",&t2);
data[i][j] = t2 + n1;
}
}
for (int i = n1 + 1; i <= n1 + n2; i++)
{
s[i] = n1;
for (int j = 1; j <= s[i]; j++)
data[i][j] = j;
}
}
bool find(int a)
{
int x;
for (int i = 1; i <= s[a]; i++)
{
x = data[a][i];
if (!state[x]) //如果节点i与a相邻并且未被查找过
{
state[x] = true; //标记i为已查找过
if (result[x] == 0 //如果i未在前一个匹配M中
|| find(result[x])) //i在匹配M中，但是从与i相邻的节点出发可以有增广路
{
result[x] = a; //记录查找成功记录
return true; //返回查找成功
}
}
}
return false;
}
int main()
{
while (scanf("%d%d",&n1,&n2)!=EOF)
{
init();
for (int i = 1; i <= n1; i++)
{
memset(state,0,sizeof(state)); //清空上次搜索时的标记
if (find(i)) ans++; //从节点i尝试扩展
}
printf("%d\n",ans);
}
return 0;
}
F 芝麻开门
动态规划。dp[i] 代表能走到i号门的方案数。反方向考虑，那么dp[i] = n^n - 不能走到i的方案数。枚举最远能够走到的距离j，那么j + 1 ~ i 这些房间的第二个钥匙就可以随便安放。于是dp[i] = n ^ n - sigma(dp[j] * i ^ (i - j))。
如果每次都i 的 i - j 次方会超时，于是方法是预处理数组 p[i][j] 代表 i ^ j 对Mod 取余数
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
typedef double db;
typedef long long LL;
const db EPS = 1e-6;
const db PI = acos(-1.0);
int sign(db x){return x < - EPS ? - 1 : x > EPS ; }
const int P = 20121215 ;
const int MAXN = 102 ;
LL pw[ MAXN ][ MAXN ];
LL c[ MAXN ][ MAXN ];
LL g[ MAXN ][ MAXN ], f[ MAXN ][ MAXN ];
void pre(){
for(int i=0;i<MAXN;++i) for(int j=0;j<=i;++j) if(i==0||j==0) c[i][j]=1; else c[i][j]=(c[i-1][j]+c[i-1][j-1])%P;
for(int i=0;i<MAXN;++i) {
pw[i][0]=1;
for(int j=1;j<MAXN;++j) pw[i][j]=pw[i][j-1]*i%P;
}
for(int i=1;i<MAXN;++i) for(int j=1;j<MAXN;++j){
for(int k=1;k<=i;++k) g[i][j]=(g[i][j] + c[i][k]*pw[j-1][i-k])%P;
}
}
void dp(int n){
-- n;
memset(f,0,sizeof f);
for(int i = 1; i <= n; ++ i) {
f[i][i]=1;
}
for(int i=2;i<= n;++i) for(int j=1;j<i;++j){
for(int len=1;len <= i-j; ++ len) {
f[i][j]=(f[i][j]+f[i-j][len]*g[len][i+1])%P;
}
//printf("f[%d,%d]=%d\n", i, j, f[i][j]);
}
LL ans = 0;
for(int i = 1; i <= n; ++ i) ans = (ans + f[n][i]*pw[n+1][i])%P;
if(!n)ans=1;
printf("%d\n", (int)ans);
}
int main(){
pre();
int n;
while( cin >> n){
dp(n);
}
return 0;
}
G 求程序的解
其实程序的含义很简单，定义区间[i , j] 为好区间——如果区间内重复次数最多的数重复次数 <= k 即可。
两种方法：
1、标程的方法实在是弱爆了——双指针+映射二叉堆，动态维护区间内重复次数最多的数的重复次数。如果重复次数>k 次那么尾指针++，直到重复次数<=k 的时候也就是求出来对于头指针为末尾的区间最前面可以到尾指针的区间。于是每次加上头指针-尾指针+1 即可。需要用Longlong
2、大家的方法是：因为如果对于区间[l , r] 是好区间的话，那么如果[l , r+1] 不是好区间则一定是a[r] 那个数字多余k次了，那么移动l，并且减少a[l] 的出现次数即可。
不过两个方法的时间复杂度都是O(nlogn)
Code1：用到C++ STL 的Map 方便计算
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <map>
#define N 100005
using namespace std;
int n , k , a[N] , T;
long long ans;
map<int ,int> h;
int main()
{
int i , j , x , y;
scanf("%d",&T);
while (T --)
{
ans = 0; h.clear();
scanf("%d %d",&n,&k);
for (i = 1 ; i <= n ;i ++)
scanf("%d",&a[i]);
x = 1;
for (i = 1 ; i <= n ;i ++)
{
h[a[i]] ++;
if (h[a[i]] > k)
{
while (a[x] != a[i])
h[a[x]] -- , x ++;
h[a[x]] -- , x ++;
}
ans += (i - x + 1);
}
cout << ans << endl;
}
return 0;
}
Code2： 排序+二分查找
#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
int a[100001] , n , k;
int T;
const int Max=100001;
int a2[Max];
int a3[Max];
int a4[Max];
void binary(int l,int r)
{
int i=l;
int j=r;
int mid=a[(l+r)/2];
int temp;
do{
while (a[i] < mid)
i++;
while (a[j] > mid)
j--;
if (i <= j)
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
temp = a2[i];
a2[i] = a2[j];
a2[j] = temp;
i++;
j--;
}
}while (i <= j);
if (i < r) binary(i,r);
if (l < j) binary(l,j);
}
int main()
{
scanf("%d" , &T);
long long ans;
while(T--){
int i ,j;
memset(a4,0,sizeof(a4));
scanf("%d%d" , &n , &k);
for (i = 1 ; i <= n ; ++i) {scanf("%d" , &a[i]);a2[i]=i;}
binary(1,n);
a3[a2[1]] = 1;
int result;
result=1;
for (i=2;i<=n;i++)
{
if (a[i]==a[i-1])
a3[a2[i]] = result;
else
{
result++;
a3[a2[i]] =result;
}
}
j=0;
ans=0;
for (i=1;i<=n;i++)
{
while (a4[a3[j+1]]<k&&j<n)
{
a4[a3[j+1]]++;
j++;
}
ans+=(long long) (j-i+1);
a4[a3[i]]--;
}
cout<<ans<<endl;
}
//system("pause");
return 0;
}
H 排队编程啦
矩阵乘法 + 概率dp / 容斥原理。
很容易能够想到转移矩阵DP[10* 10] （就是原来的矩阵）。对于一开始的概率向量{0.1,0.1….0.1} Start, 我们只需要算——概率向量End = Start * {E + DP + DP^2 +…+DP^(n - 1)}就可以算出最后一个数字的概率向量End。至于矩阵等比数列求和的方法请见POJ
3233
3233
然后用容斥原理计算——每个数字至少出现一次的期望。
Code1：容斥原理 标程
const int MATN = 10;
struct Mat{
int Matn , Matm;
double a[MATN][MATN];
Mat(){
Matn = 0;
Matm = 0;
memset(a , 0 , sizeof(a));
}
void output(){
cout << "OUTPUT" << endl;
for (int i = 0 ; i < Matn ; ++i){
for (int j = 0 ; j < Matm ; ++j){
printf("%.3lf ",a[i][j]);
}
printf("\n");
}
}
void init(){
Matn = 0;Matm = 0;
memset(a , 0 , sizeof(a));
}
Mat operator + (const Mat & A) const{
Mat ret = A;
for (int i = 0 ; i < Matn ; ++i){
for (int j = 0 ; j < Matm ; ++j)
ret.a[i][j] = (ret.a[i][j] + a[i][j]);
}
return ret;
}
Mat operator * (const Mat & A) const{
Mat c ;
c.Matn = Matn;
c.Matm = A.Matm;
for (int i = 0 ; i < Matn ; ++i)
for (int j = 0 ; j < A.Matm ; ++j)
for (int k = 0 ; k < Matm ; ++k)
c.a[i][j] = (c.a[i][j] + (a[i][k] * A.a[k][j]));
return c;
}
void initI(){
memset(a, 0 , sizeof(a));
for (int i = 0 ; i < Matn ; ++i)
a[i][i] = 1;
}
Mat power(LL k){
Mat c = *this , b;
b.init();
b.Matn = Matn ; b.Matm = Matm;
b.initI();
while(k){
if (k & 1LL)
b = b * c;
c = c * c;
k >>= 1LL;
}
return b;
}
} p , res , ansMat;
struct ZHU{
Mat a[2][2];
void init(Mat p){
for (int i = 0 ; i < 2 ; ++i)
for (int j= 0 ; j < 2 ;++j){
a[i][j].init();
a[i][j].Matn = a[i][j].Matm = 10;
}
a[0][0] = p;
a[0][1].initI();
a[1][1].initI();
}
void initI(){
for (int i = 0 ; i < 2 ; ++i)
for (int j= 0 ; j < 2 ;++j){
a[i][j].Matn = a[i][j].Matm = 10;
a[i][i].initI();
}
}
ZHU operator * (const ZHU & A) const{
ZHU res;
for (int i = 0 ; i < 2 ; ++i)
for (int j= 0 ; j < 2 ;++j){
res.a[i][j].init();
res.a[i][j].Matn = res.a[i][j].Matm = 10;
}
for (int i = 0 ; i < 2 ; ++i)
for (int j = 0 ; j < 2 ; ++j)
for (int k = 0 ; k < 2 ; ++k)
res.a[i][j] = (res.a[i][j] + a[i][k] * A.a[k][j]);
return res;
}
Mat power(LL k){
ZHU c = *this , b;
bool f = false;
while(k){
if (k & 1LL){
if (!f) b = c;
else b = b * c;
f = true;
}
c = c * c;
k >>= 1LL;
}
if (!f){
b = c;
b.a[0][1].initI();
}
return b.a[0][1];
}
} q;
LL n ;
void solve(){
scanf("%lld" , &n);
p.init();
p.Matn = p.Matm = 10;
for (int i = 0 ; i < 10 ; ++i)
for (int j = 0 ; j < 10 ; ++j){
scanf("%lf" , &p.a[i][j]);
p.a[i][j] /= 100.0;
}
q.init(p);
ansMat.init();
ansMat.Matn = 1 ; ansMat.Matm = 10;
for (int i = 0 ; i < 10 ; ++i)
ansMat.a[0][i] = 0.1;
res = q.power(n);
ansMat = ansMat * res;
for (int i = 0 ; i < 10 ; ++i){
ansMat.a[0][i] /= (double)(n);
//cout << ansMat.a[0][i] << endl;
}
double ans = 0;
for (int i = 1 ; i < (1 << 10) ; ++i){
int ii = i;
double sump = 0;
int jud = 0;
for (int j = 0 ; j < 10 && ii ; ++j){
if (ii & 1){
sump += ansMat.a[0][j];
jud ^= 1;
}
ii >>= 1;
}
if (jud) ans += 1.0 / sump;
else ans -= 1.0 / sump;
}
printf("%.3lf\n" , ans);
}
int main(){
freopen("0.in" , "r" , stdin);
freopen("1.out" , "w" , stdout);
int _;
cin >> _;
int __ = 0;
while (_--){
cout << ++__ << " = ";
solve();
}
}
Code2： 递归写法
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
#define PI acos(-1.0)
#define eps 1e-9
#define MOD ((ll)100000*100000+7)
#define INF 1000000000
using namespace std;
template<class T> T f_min(T x,T y){return x<y?x:y;}
template<class T> T f_max(T x,T y){return x>y?x:y;}
template<class T> T f_abs(T x){return x<0?-x:x;}
int R=20;
struct Matrix{
double v[25][25];
void set(){
int i,j;
for(i=0;i<10;i++){
for(j=0;j<10;j++){
v[i+10][j]=0;
v[i+10][j+10]=0;
v[i][j+10]=0;
}
}
for(i=0;i<10;i++){
v[i][i+10]=1;
v[i+10][i+10]=1;
}
}
void ini(){
int i,j;
for(i=0;i<R;i++){
for(j=0;j<R;j++){
v[i][j]=0;
}
}
for(i=0;i<R;i++)v[i][i]=1;
}
void disp(){
int i,j;
for(i=0;i<R;i++){
for(j=0;j<R;j++){
printf("%.1lf ",v[i][j]);
}
printf("\n");
}
}
};
ll N;
Matrix mat;
void get_data(){
scanf("%lld",&N);
int i,j;
for(i=0;i<10;i++){
for(j=0;j<10;j++){
scanf("%lf",&mat.v[i][j]);
mat.v[i][j]/=100;
}
}
}
Matrix mul(Matrix &A,Matrix &B){
Matrix r;
int i,j,k;
for(i=0;i<10;i++){
for(j=0;j<R;j++){
r.v[i][j]=0;
}
}
for(j=0;j<R;j++){
r.v[i][j]=0;
for(k=0;k<R;k++){
if(B.v[k][j]<1e-6)continue;
for(i=0;i<10;i++){
r.v[i][j]+=A.v[i][k]*B.v[k][j];
}
}
}
for(i=10;i<20;i++){
for(j=0;j<R;j++){
r.v[i][j]=A.v[i][j];
}
}
return r;
}
Matrix f_mul(ll n){
Matrix r;
r.ini();mat.set();
// mat.disp();
while(n){
if(n&1){
r=mul(r,mat);
}
n>>=1;
mat=mul(mat,mat);
// mat.disp();
}
// r.disp();
return r;
}
double pos[20];
double res;
void dfs(int loc,int n,double v){
if(loc==10){
if(n==0)return;
// if(f_abs(v)<eps)return;
// printf("%lf %.20lf\n",res,v);
// getchar();
if(n&1)res+=1/v;
else res-=1/v;
return;
}
dfs(loc+1,n,v);
dfs(loc+1,n+1,v+pos[loc]);
}
void run(){
Matrix mt=f_mul(N);
int i,j;
// mt.disp();
for(j=10;j<20;j++){
pos[j-10]=0;
for(i=0;i<10;i++)pos[j-10]+=mt.v[i][j]/N/10;
// printf("%d %.20lf\n",j-10,pos[j-10]);
}
res=0;
dfs(0,0,0);
printf("%.4lf\n",res);
}
int main(){
int t;
scanf("%d",&t);
while(t--){
get_data();
run();
}
return 0;
}
I Move The Box
搜索 + 模拟
只要写好了 按照重力下降的函数 还有 判断爆炸的函数 ， 之后就是广度优先搜索或者迭代加深深度优先搜索的方法了。因为广度优先搜索要记录状态，所以不可避免地慢了很多。
Code 1 ： bfs
const int N = 8;
int n , m;
bool inmap(int x , int y){
return 0 <= x && x < n && 0 <= y && y < m;
}
const int dir[][2] = {{1 , 0} , {0 , -1} , {0 , 1}};
map<char , int> cnt;
int explode[N][N] , T_T;
struct Box{
char str[N][N];
bool operator < (const Box & A) const{
for (int i = 0 ; i < n ; ++i)
for (int j = 0 ; j < m ; ++j)
if (str[i][j] != A.str[i][j])
return str[i][j] < A.str[i][j];
return false;
}
PUU hashCode(){
PUU ret;ret.fi = 0 , ret.se = 0;
for(int i = 0 ; i < n ; ++i){
for(int j = 0 ; j < m ; ++j)
ret.fi = ret.fi * (ULL)209 + str[i][j] , ret.se = ret.se * (ULL)681 + str[i][j];
}
return ret;
}
int sum , s;
bool lose(){
cnt.clear();
for (int i = 0 ; i < n ; ++i)
for (int j = 0 ; j < m ; ++j){
if (str[i][j] == '.') continue;
++cnt[ str[i][j] ];
}
ECH(iter , cnt){
if (iter -> second <= 2) return true;
}
return false;
}
bool crash(){
//RST(explode);
++T_T;
bool ret = false;
for (int i = 0 ; i < n ; ++i){
for(int j = 0 ; j < m ; ++j){
if (str[i][j] == '.') continue;
for (int d = 0 ; d < 3 ; ++d){
bool cancrash = inmap(i + dir[d][0] , j + dir[d][1]) && inmap(i + 2 * dir[d][0] , j + 2 * dir[d][1]);
cancrash &= str[ i + dir[d][0] ][j + dir[d][1] ] == str[i][j];
cancrash &= str[ i + 2 * dir[d][0] ][j + 2 * dir[d][1] ] == str[i][j];
ret |= cancrash;
if (cancrash){
explode[i][j] = T_T;
explode[i + dir[d][0] ][j + dir[d][1] ] = T_T;
explode[i + 2 * dir[d][0] ][j + 2 * dir[d][1] ] = T_T;
}
}
}
}
if (ret){
for (int i = 0 ; i < n ; ++i)
for (int j = 0 ; j < m ; ++j){
if (explode[i][j] == T_T)
str[i][j] = '.';
}
}
return ret;
}
void falldown(){
sum = 0;
for (int j = 0 ; j < m ; ++j){
int ii = n - 1;
for (int i = n - 1 ; i >= 0 ; --i){
if (str[i][j] != '.') {
sum ++;
char tmp = str[i][j];
str[i][j] = '.';
str[ii--][j] = tmp;
}
}
}
}
bool win(){
return sum == 0;
}
void gao(){
do{
falldown();
}while ( crash() ) ;
}
void input(){
sum = 0;
for (int i = 0 ; i < n ; ++i){
scanf("%s" , str[i]);
for (int j = 0 ; j < m ; ++j)
sum += (str[i][j] != '.');
}
}
bool canmove(int x , int y , int d){
if (str[x][y] == '.') return false;
if (d == 0 && x == n - 1) return false;
if (d == 1 && y == 0) return false;
if (d == 2 && y == m - 1) return false;
return true;
}
void move(int x , int y , int d){ //0 down , 1 left , 2 right
swap(str[x][y] , str[x + dir[d][0]][y + dir[d][1]]);
}
void output(){
for (int i = 0 ; i < n ; ++i){
printf("%s\n" , str[i]);
}
}
}st;
Box lis[2000000];
int head , tail;
int pre[2000000];
const string Movename[] = {"Down" , "Left" , "Right"};
set<PUU> hash;
struct Movements{
int x , y , d;
Movements(){}
Movements(int _x , int _y , int _d):x(_x) , y(_y) , d(_d) {}
void output(){
printf("%d %d %s\n" , n - x , y + 1 , Movename[d].c_str());
}
}steppre[2000000];
vector< Movements > ans;
int anstail;
void bfs(){
head = -1 , tail = 0;
st.s = 0;
lis[0] = st ; pre[0] = -1;
Box now , go;
hash.clear();
hash.insert(st.hashCode());
while(head < tail){
++head;
//system("pause");
now = lis[head];
if (now.s == 3) continue;
for (int i = n - 1 ; i >= 0 ; --i)
for (int j = 0 ; j < m ; ++j){
if (now.str[i][j] == '.') continue;
for (int d = 0 ; d < 3 ; ++d){
if (!now.canmove(i , j , d)) continue;
go = now;
go.move(i , j , d);
go.gao();
PUU gohashCode = go.hashCode();
if (go.lose() || hash.find(gohashCode) != hash.end()) continue;
go.s = now.s + 1;
hash.insert(gohashCode);
lis[ ++tail ] = go;
steppre[tail] = Movements(i , j , d);
pre[tail] = head;
if (go.win()) {
anstail = tail;return;
}
}
}
}
}
void output(int p){
if (pre[p] != -1) {
output( pre[p] );
ans.PB( steppre[p] );
}
}
void solve(){
RD(n , m);
st.input();
//printf("%s\n" , st.str[n - 1]);
bfs();
ans.clear();
output(anstail);
printf("%d\n" , SZ(ans));
for (int i = 0 ; i < SZ(ans) ; ++i){
ans[i].output();
}
//printf("%d\n" , tail);
printf("\n");
}
int main(){
freopen("0.in" , "r" , stdin);
freopen("0.out" , "w" , stdout);
RST(explode);
Rush solve();
}
Code2： 最快的dfs
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <cstdio>
#include <algorithm>
#define N 12
using namespace std;
int n , m , T , maxdep;
char s[N][N] ;
bool f[N][N];
int ax[4] , ay[4] , ad[4];
void fall(int x , int y)
{
if (x > 1 && s[x][y] == '.' && s[x - 1][y] != '.')
swap(s[x - 1][y] , s[x][y]) , fall(x - 1 , y);
}
void print()
{
int i , j;
for (i = 1 ; i <= n ;i ++)
{
for (j = 1 ; j <= m ;j ++)
printf("%c",s[i][j]);
printf("\n");
}
printf("\n");
}
void work(int& sum)
{
//print();
if (!sum) return;
int i , j;bool u = 0;
memset(f , 0 , sizeof(f));
for (i = 1 ; i <= n ;i ++)
for (j = 1 ; j <= m ;j ++)
if (s[i][j] != '.')
{
if (s[i][j] == s[i][j - 1] && s[i][j] == s[i][j + 1]) f[i][j] = 1;
if (s[i][j] == s[i][j - 1] && s[i][j] == s[i][j - 2] && j > 2) f[i][j] = 1;
if (s[i][j] == s[i][j + 1] && s[i][j] == s[i][j + 2]) f[i][j] = 1;
if (s[i][j] == s[i + 2][j] && s[i][j] == s[i + 1][j]) f[i][j] = 1;
if (s[i][j] == s[i - 1][j] && s[i][j] == s[i + 1][j]) f[i][j] = 1;
if (s[i][j] == s[i - 1][j] && s[i][j] == s[i - 2][j] && i > 2) f[i][j] = 1;
}
for (i = 1 ; i <= n ;i ++)
for (j = 1 ; j <= m ;j ++)
if (f[i][j])
sum -- , s[i][j] = '.' , fall(i , j) , u = 1;
if (u) work(sum);
}
bool dfs(int dep , int sum)
{
//print();
if (sum == 0)
return 1;
if (dep == maxdep)
return 0;
int i , j , x , S = sum; char t[N][N] = {};
for (i = 1 ; i <= n ;i ++)
for (j = 1 ; j <= m ;j ++)
t[i][j] = s[i][j];
for (i = 1 ; i <= n ;i ++)
for (j = 1 ; j <= m ;j ++)
if (s[i][j] != '.')
{
if (j > 1 && s[i][j - 1] == '.' )
{
swap(s[i][j] , s[i][j - 1]), fall(i , j);
x = i + 1;
while (s[x][j - 1] == '.')
fall(x,j - 1) , ++ x;
work(sum);
ax[dep] = i , ay[dep] = j , ad[dep] = 1;
if (dfs(dep + 1 , sum)) return 1;
for (int q = 1 ; q <= n ;q ++)
for (int w = 1 ; w <= m ;w ++)
s[q][w] = t[q][w]; sum = S;
}
if (j < m && s[i][j] != s[i][j + 1])
{
swap(s[i][j] , s[i][j + 1]), fall(i , j);
x = i + 1;
while (s[x][j + 1] == '.')
fall(x,j + 1) , ++ x;
work(sum);
ax[dep] = i , ay[dep] = j , ad[dep] = 2;
if (dfs(dep + 1 , sum)) return 1;
for (int q = 1 ; q <= n ;q ++)
for (int w = 1 ; w <= m ;w ++)
s[q][w] = t[q][w]; sum = S;
}
if (i > 1 && s[i - 1][j] != '.' && s[i - 1][j] != s[i][j])
{
swap(s[i - 1][j] , s[i][j]);
work(sum);
ax[dep] = i , ay[dep] = j , ad[dep] = 3;
if (dfs(dep + 1 , sum)) return 1;
for (int q = 1 ; q <= n ;q ++)
for (int w = 1 ; w <= m ;w ++)
s[q][w] = t[q][w]; sum = S;
}
}
}
int main()
{
scanf("%d\n",&T);
int i , j, sum , t[N][N];
while (T --)
{
sum = 0;
scanf("%d %d\n",&n,&m);
memset(s , 0 ,sizeof(s));
memset(t , 0 ,sizeof(t));
for (i = 1 ; i <= n ;i ++)
scanf("%s\n",s[i] + 1);
for (i = 1 ; i <= n ;i ++)
for (j = 1 ; j <= m ;j ++)
t[i][j] = s[i][j];
for (i = 1 ; i <= n ;i ++)
for (j = 1 ; j <= m ;j ++)
if (s[i][j] != '.')
sum ++;
for (maxdep = 1 ; maxdep <= 3 ; maxdep ++)
{
if (dfs(0 , sum))
{
printf("%d\n",maxdep);
for (i = 0 ;i < maxdep ; i ++)
{
printf("%d %d ",n - ax[i] + 1, ay[i]);
if (ad[i] == 1)
printf("Left\n");
if (ad[i] == 2)
printf("Right\n");
if (ad[i] == 3)
printf("Up\n");
}
break;
}
for (i = 1 ; i <= n ;i ++)
for (j = 1 ; j <= m ;j ++)
s[i][j] = t[i][j];
}
printf("\n");
}
return 0;
}
J 快来打飞机
查资料+数学公式计算。
标程是用Java的固有函数。。
#include <iostream>
#include <math.h>
#include <stdio.h>
using namespace std;
struct Tpoint {
double x, y, z;
Tpoint() {}
Tpoint (double _x, double _y, double _z): x(_x), y(_y), z(_z) {}
Tpoint operator - (const Tpoint &p) { return Tpoint (x-p.x, y-p.y, z-p.z); }
Tpoint operator * (const Tpoint &p) //叉积
{ return Tpoint (y*p.z-z*p.y, z*p.x-x*p.z, x*p.y-y*p.x); }
double operator ^ (const Tpoint &p) //点积
{ return x*p.x + y*p.y + z*p.z; }
};
double dis (Tpoint a) { return sqrt(a.x*a.x + a.y*a.y + a.z*a.z); }
int main()
{
double dx, dy, dz, lz;
Tpoint a, b, v, X, Y;
while (~scanf ("%lf%lf%lf%lf%lf%lf", &a.x, &a.y, &a.z, &b.x, &b.y, &b.z))
{
v = b - a;
dz = (v^a) / dis (a);
Tpoint z(0, 0, 1);
lz = (a.x*a.x+a.y*a.y+a.z*a.z)/(z^a);
z.z = lz;
Y = z - a;
dy = (v^Y) / dis(Y);
X = Y * a;
dx = (v^X) / dis(X);
printf ("%.5f %.5f %.5f\n", dx, dy+5000, dz-5000);
}
return 0;
}
K 发气球啦
杂题 + 字符串处理
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cmath>
#include <vector>
#include <cstdio>
#include <algorithm>
#define N 25005
using namespace std;
string s[15];
string ac = "Accepted - 1";
int n;
int main()
{
while (getline(cin, s[n]))
{
if (s[n].find(ac , 15) != string::npos)
{
int x = (n + 13) % 15;
for (int i = 26 ; s[x][i] != 34 ; i ++)
cout << s[x][i];
cout << ' ';
cout << s[(n + 5) % 15][37] << ' ' ;
x = (n + 8) % 15;
for (int i = 34 ; s[x][i] != 47 ; i ++)
cout << s[x][i];
cout << endl;
}
n = (n + 1) % 15;
}
return 0;
}
最后感谢大家的支持和配合，恭喜赵轩昂同学唯一一个AK了所有题目。
并且对几次Rej对于大家的不便表示歉意。
对于抄袭代码的同学，要重罚，直接取消资格。希望大家下次做到公平公正
如果有错误欢迎大家及时指正。
Kissbuaa 董适