NOIP2017金秋冲刺训练营杯联赛模拟大奖赛第一轮Day2
期望得分:100+100+ =200+
实际得分:100+40+70=210
T1天天寄快递
直接模拟,代码丢了。。。。。。
T2天天和不可描述
splay可A
正解dfs+list
#include<iostream>
#include<list>
#include<cstdio>
using namespace std;
list<char>s;
char c;
void getstr(bool rev,list<char>&tmp)
{
tmp.clear();
while(true)
{
c=cin.get();
if(c==')') break;
else if(c=='(')
{
list<char>tmp2;
getstr(!rev,tmp2);
if(rev) s.splice(tmp.begin(),tmp2);
else s.splice(tmp.end(),tmp2);
}
else if(rev) tmp.push_front(c);
else tmp.push_back(c);
}
}
int main()
{
while()
{
c=cin.get();
if(c==EOF) break;
else if(c=='(')
{
list<char>tmp;
getstr(true,tmp);
s.splice(s.end(),tmp);
}
else s.push_back(c);
}
for(list<char>::iterator iter=s.begin();iter!=s.end();iter++) cout<<*iter;
return ;
}
T3 罪犯分组
状压DP
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
bool map[][];
int f[<<|];
int main()
{
int n,m,k,u,v;
scanf("%d%d%d",&n,&m,&k);
for(int i=;i<=m;i++) scanf("%d%d",&u,&v),u--,v--,map[u][v]=map[v][u]=true;
memset(f,,sizeof(f));
int S=<<n;
f[]=;
int sum;
for(int i=;i<S;i++)
{
sum=;
for(int j=;j<n;j++)
for(int k=j+;k<n;k++)
if((<<k)&i && (<<j)&i && map[j][k]) sum++;
if(sum<=k) f[i]=;
for(int j=i;j;j=(j-)&i) f[i]=min(f[i],f[j]+f[j^i]);
}
printf("%d",f[S-]);
}