做的练习赛，已补全
A。水题~但是出了个很神奇的错误。
return “NO”。我居然把O打成0了。。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 2005
#define inf 1<<28
#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
#define FOR(i,s,t) for(int i=(s);i<=(t);++i)
#define ll long long
using namespace std;
bool cmp(int a,int b)
{
return a>b;
}
class CucumberMarket {
public:
string check(vector <int> price, int budget, int k) {
int num=price.size();
int *a=new int[num];
for(int i=0;i<num;i++)
a[i]=price[i];
sort(a,a+num,cmp);
int sum=0;
for(int i=0;i<k&&i<num;i++)
sum+=a[i];
if(sum>budget)
return "NO";
else
return "YES";
}
};
B，模拟题，讲每个'B'标记一下，然后每找到一个‘B’，则从这里开始，沿着对角线遍历，找出下一个‘B’，比较两个之间的距离，sum+=min(两者的距离，T),因为有可能两个‘B’之间形不成直线，因为T的次数太小，所以得找出最小值。
int num[100][100];
class PastingPaintingDivTwo {
public:
long long countColors(vector <string> clipboard, int T) {
memset(num,0,sizeof(num));
int n,m;
for(int i=0;i<clipboard.size();i++)
{
n=clipboard.size();
for(int j=0;j<clipboard[i].length();j++)
{
m=clipboard[i].length();
if(clipboard[i][j]=='B')
{
num[i][j]++;
}
}
}
ll sum=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
int spn=0;
int k;
int spp=0;
if(num[i][j])
{
for(k=0;k<=min(n-i,m-j);k++)
{
if(num[i+k][j+k])
{
spp+=spn;
spn=k-spp;
sum+=min(spn,T);
}
num[i+k][j+k]=0;
}
//sum+=spn;
sum+=T;
}
}
}
return sum;
}
};
C.又是悲剧的一题，第一交了发现数据溢出了，得用long long 存。。太大意了。一开始死都找不到哪里错了，最后烦起来就把所有的数据类型都改成了long long ,没想到过了。过了。。。。了。。。。
太粗心了。
题意很简单，就是给你两组数a[],b[]，和一个数字的总数，叫你算出所有a[i],b[i]不相邻的概率。
状压，dp[i][j][k]表示第i位是j的k状态的总数。
ll t;
ll dp[15][15][1<<15];
class RandomOption
{
public:
double getProbability(int keyCount, vector <int> badLane1, vector <int> badLane2)
{
bool Map[15][15]= {0};
for(int i=0; i<badLane1.size(); i++)
{
Map[badLane1[i]][badLane2[i]]=Map[badLane2[i]][badLane1[i]]=1;//标记，不能相邻
}
for(int i=0; i<keyCount; i++)dp[1][i][1<<i]=1;
t=1ll;
for(int i=1; i<=keyCount; i++)t*=i; //总状态数 即是，keyCount!
for(int i=0; i<keyCount; i++)//i位
{
for(int j=0; j<keyCount; j++)//是j
{
for(int k=0; k<1<<keyCount; k++)//枚举所有状态
{
for(int l=0; l<keyCount; l++)//往j后面加l
{
if(Map[j][l]||Map[l][j])continue;// 如果l和j是badLane，则不能相邻
if((k>>l)&1)continue;//或者j的状态里已经有了l。
int nn=k|(1<<l);
dp[i+1][l][nn]+=dp[i][j][k];//第i+1位为l的总状态数。
}
}
}
}
ll ans=0;
for(int i=0; i<keyCount; i++)
ans+=dp[keyCount][i][(1<<keyCount)-1];//所有非badLane的状态数
return (double)ans/t;
}
};
//这个只是一个样例，可以跑跑看。
int main()
{
RandomOption a;
vector<int>q;
q.push_back(0);
vector<int >p;
p.push_back(1);
cout<<a.getProbability(14,q,p)<<endl;//这个样例就是让dp溢出int的数据。跪了。。。正确答案貌似是0.8....多少多少的。
return 0;
}