（本套题算是比较温和吧，就是罚时有点高。
B .Baby Bites
题意：给出一个婴儿给出的数组，有一些数字听不清楚，让你还原，问它是否是一个从1开始的一次增加的数组。
思路：从左往右依次固定，看是否有矛盾即可。
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define rep2(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
int a[]; char c[];
int main()
{
int N; bool F=true;
scanf("%d",&N);
rep(i,,N) {
scanf("%s",c+);
if(c[]=='m') a[i]=-;
else {
int L=strlen(c+);
rep(j,,L) a[i]=a[i]*+c[j]-'';
}
}
if(a[]==-) a[]=;
if(a[]!=) F=false;
rep(i,,N) {
if(a[i]==-&&a[i-]!=-) a[i]=a[i-]+;
if(a[i]!=-&&a[i-]!=-)
if(a[i]!=a[i-]+) F=false;
}
if(F) puts("makes sense");
else puts("something is fishy");
return ;
}
C .Code Cleanups
题意：给定N个物体，每个物品需要在第几天清扫。 你每次可以选择其中几个清扫，但是要满足你选择的集合拖欠的天数之和<20；问最小的清扫次数。
思路：贪心地取即可。
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int a[];
int main()
{
int N,ans=; scanf("%d",&N);
rep(i,,N) scanf("%d",&a[i]);
rep(i,,N){
int now=,sum=,j=i; ans++;
while(j+<=N&&(sum+now*(a[j+]-a[j]))<)
sum+=now*(a[j+]-a[j]),now++,j++;
i=j;
}
printf("%d",ans);
return ;
}
E. Explosion Exploit
题意：给定N个自己人，M个敌人。以及每个人的血量ai。系统一共发起K次攻击，每次随机选择一个人物进行攻击，被攻击后血量少1，血量为0的不再考虑。问最后敌人都被杀死的概率。 （N,M<=5 ,ai<=6,K<=100）
思路：因为数据都比较小，我们可以考虑记忆化搜索，显然我们不能开10维数组来模拟，空间不够。 我们需要维护两个集合，分别是自己人的血量和敌人的血量，然后记忆化搜索。 集合我们可以用vector来表示，每次向下搜索前vector可以先排序，这样可以减很多的枝。 我的代码没用数组表示集合，用的是long long。
因为魔改了几次，所以代码比较丑。
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
map<ll,double>mp; int N,M,K;
int a[],b[],sum,FCY; ll P[];
int c[],cnt;
void Change(ll &x){ //集合内部排序
ll res=;
for(int i=N;i>=;i--) a[i]=x%,x/=;
for(int i=M;i>=;i--) b[i]=x%,x/=;
sort(a+,a+N+); sort(b+,b+M+);
rep(i,,M) res=res*+b[i],c[N+M+-i]=b[i];
rep(i,,N) res=res*+a[i],c[N+-i]=a[i];
cnt=; rep(i,,N) if(a[i]) cnt++; rep(i,,M) if(b[i]) cnt++;
x=res;
}
double dfs(ll Now,int D)
{
Change(Now); int num=cnt,d[];
rep(i,,N+M) d[i]=c[i];
if(mp.find(Now)!=mp.end()) return mp[Now];
if(Now<FCY) return mp[Now]=1.0;
if(D==) return mp[Now]=0.0;
double res=;
rep(i,,N+M) {
if(d[i]==) continue;
d[i]--; if(d[i]==) num--;
res+=dfs(Now-P[i-],D-)/(num+(d[i]==));
if(d[i]==) num++; d[i]++;
} return mp[Now]=res;
}
int main()
{
scanf("%d%d%d",&N,&M,&K);
rep(i,,N) scanf("%d",&a[i]),sum+=a[i];
rep(i,,M) scanf("%d",&b[i]),sum+=b[i];
if(K>=sum) return puts("1.00000000"),;
ll Now=; FCY=; P[]=; cnt=N+M;
rep(i,,N+M) P[i]=P[i-]*;
rep(i,,M) Now=Now*+b[i],c[N+M+-i]=b[i];
rep(i,,N) Now=Now*+a[i],FCY*=,c[N+-i]=a[i];
printf("%.8lf\n",dfs(Now,K));
return ;
}
H .House Lawn
by 许
#include<bits/stdc++.h>
#define db double
#define ll long long
using namespace std;
const int maxn=1e6+,inf=1e9;
char str[];
struct node
{
char s[];
int id,p;
bool operator<(const node&t)const
{
if(p==t.p)return id<t.id;
return p<t.p;
}
}a[];
void gao(int cur,int &pri,int &c,int &t,int &r)
{
int n=strlen(str),i=;
pri=c=t=r=;
while(str[i]!=',')i++;
i++;
while(str[i]!=',')
pri=pri*+str[i++]-'';i++;
while(str[i]!=',')
c=c*+str[i++]-'';i++;
while(str[i]!=',')
t=t*+str[i++]-'';i++;
while(i<n)
r=r*+str[i++]-'';
}
int main()
{
int e,m,pri,c,t,r,v,n=,cnt=;
cin>>e>>m;
getchar();
for(int i=;i<=m;i++)
{
gets(str);
gao(i,pri,c,t,r);
v=n/(t+r)*t*c;
if(v<e)
{
int tmp=n%(t+r);
db v1=(db(e)-v)/c,v2=tmp-v1;
if(v1<=(db)t)
if(v1*r<=v2*t)v=e;
}
if(v>=e)
{
a[++cnt].p=pri; a[cnt].id=i;
int len=strlen(str),j=;
while(str[j]!=',')
a[cnt].s[j]=str[j],j++;
a[cnt].s[j]='\0';
}
}
sort(a+,a++cnt);
if(cnt==)puts("no such mower");
else
{
int i=;
while()
{
printf("%s\n",a[i++].s);
if(i>cnt||a[i].p>a[i-].p)break;
}
}
}
I .Intergalactic Bidding
题意：给出N个高精度数，表示N个人对应的数字，满足每个人的数字大于等于前面一个人的两倍，以及S。 输出winners，一个人是winner，当且仅当他存在一个集合里，这个集合是和是S。
思路：首先挖掘为何有大于等于两倍，我们发现它告诉我们每一个集合表示出来的数都是不同的，而每一个S对应的集合也是唯一的，所以要么没有winner，要么我们可以从大到小贪心地拼凑出S。
by 罗
elect Code #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=;
const int maxn=1e6+;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
string s;
int cmp(string a,string b){
if(a.length()>b.length())return true;
else if(a.length()<b.length())return false;
else return a>=b;
}
bool vis[];
struct node{
string name;
string money;
}my[];
bool cmpp(node a,node b){
if(a.money.size()>b.money.size())return true;
else if(a.money.size()<b.money.size())return false;
else return a.money>b.money;
}
string sub(string a,string b){
string ans="";
reverse(a.begin(),a.end());
reverse(b.begin(),b.end());
int len1=a.length(),len2=b.length();
int pre=;
for(int i=;i<len2;i++){
int now=a[i]-b[i];
if(now<)a[i+]--,now=+now;
ans+=(char)(now+'');
}
for(int i=len2;i<len1;i++){
int num=a[i]-'';
if(num<){
num+=;
a[i+]--;
}
ans+=(char)(num+'');
}
while(ans.size()>&&ans.back()=='')ans.pop_back();
reverse(ans.begin(),ans.end());
return ans;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie();
std::cout.tie();
int n;
cin>>n;
cin>>s;
for(int i=;i<=n;i++){
cin>>my[i].name>>my[i].money;
}
int num=;
sort(my+,my++n,cmpp);
for(int i=;i<=n;i++){
if(cmp(s,my[i].money)){
s=sub(s,my[i].money);
vis[i]=;
num++;
}
}
if(s==""){
cout<<num<<endl;
for(int i=;i<=n;i++){
if(vis[i])cout<<my[i].name<<endl;
}
}
else{
cout<<""<<endl;
}
return ;
}
J .Jumbled String
题意： 给你00，01，10，11的数量a，b，c，d。 让你根据信息还原一个字符串 。
思路：由00和11的数量，我们可以得到字符串中0和1的数量x和y，然后取凑即可， 注意00数量为0时，x可能为0，也可能为1，其它情况下，x唯一； y同理。
假设得到了x，y。 我们可以试着构造一个形如11111...0001000....1111的串，即中间可以夹杂一个1。
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
const int Mod=1e9+;
map<int,int>mp;
bool check(int A,int D,int B,int C)// 0,1
{
if(1LL*A*D!=1LL*B+C) return false;
if(A==&&B==&&C==){
rep(i,,D) putchar(''); return true;
}
if(D==&&B==&&C==){
rep(i,,A) putchar(''); return true;
}
int num=B/A,rem=B%A;
rep(i,,D-num-(rem!=)) putchar('');
rep(i,,A) {
putchar('');
if(rem==i) putchar('');
}
rep(i,,num) putchar('');
return true;
}
int main()
{
int A,B,C,D;
rep(i,,){
int tmp;
if(i&) tmp=(i-)/*i;
else tmp=i/*(i-);
mp[tmp]=i;
}
scanf("%d%d%d%d",&A,&B,&C,&D);
if(mp[A]==) return puts("impossible"),;
if(mp[D]==) return puts("impossible"),;
if(check(mp[A],mp[D],B,C)) return ;
if(A==&&check(,mp[D],B,C)) return ;
if(D==&&check(mp[A],,B,C)) return ;
if(A==&&D==&&check(,,B,C)) return ;
puts("impossible");
return ;
}
K .King's Colors
题意：给你N，K，一棵大小为N的树，求刚好染K种色，而且相邻边颜色不同的方案数。
思路：一眼容斥题，我们用F(x)表示颜色大于等于x的方案数，则ans=F(K)*C(K,K) -F(K-1)*C(K,K-1)+F(K-2)*C(K,K-2）...
而这又是一棵树，所以我们从上到下染色，每个点只要和父亲颜色不同即可。 所以F(x)=x*(x-1)^(N-1)；
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
const int Mod=1e9+;
int C[maxn][maxn],N,K,ans;
int qpow(int a,int x)
{
int res=; while(x){
if(x&) res=(ll)res*a%Mod;
a=(ll)a*a%Mod; x>>=;
} return res;
}
int main()
{
rep(i,,) C[i][]=C[i][i]=;
rep(i,,)
rep(j,,i) C[i][j]=(C[i-][j-]+C[i-][j])%Mod;
scanf("%d%d",&N,&K);
rep(i,,N){
int u; scanf("%d",&u);
}
for(int i=K;i>=;i--){
if((K-i)%==){
(ans+=(ll)i*qpow(i-,N-)%Mod*C[K][i]%Mod)%=Mod;
}
else {
ans=((ans-(ll)i*qpow(i-,N-)%Mod*C[K][i]%Mod)%Mod+Mod)%Mod;
}
}
printf("%d\n",ans);
return ;
}