题解（伪）

T1

我没看过题。。但据说好像挺简单的。。
不写了
放一个帅爷爷的代码

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>using namespace std;typedef long long LL;const LL Maxn=100010;LL N,M,S,K;
vector<LL>V[Maxn]; LL p[Maxn];priority_queue<pair<LL,LL> >Q;int main()
{freopen("express.in","r",stdin);freopen("express.out","w",stdout);scanf("%lld%lld%lld%lld",&N,&M,&S,&K);for(LL i=1;i<=M;i++){LL e,t; scanf("%lld%lld",&e,&t);if(t>2) V[e].push_back(2-t);}for(LL i=1;i<=N;i++) sort(V[i].begin(),V[i].end());bool bk=false; LL ans=0;for(LL i=1;i<=N;i++){LL s=0;for(LL j=0;j<V[i].size();j++){s+=-V[i][j]; S--; p[i]=j+1;if(S==0 || s>=K) break;}if(s<K){
   printf("-23333333\n"); return 0;}else ans+=s;}for(LL i=1;i<=N;i++) if(p[i]!=V[i].size()) Q.push(make_pair(-V[i][p[i]],i));while(S && !Q.empty()){S--; pair<LL,LL>x=Q.top(); Q.pop();ans+=x.first; p[x.second]++;if(p[x.second]!=V[x.second].size()) Q.push(make_pair(-V[x.second][p[x.second]],x.second));}return printf("%lld\n",ans),0;
}

T2

这题就有点搞笑了。。
话说由于今早要上课，于是去麦当劳买早餐吃。。
排队的时候惊奇地发现Q群居然有题了，就看了一眼，T1太长，跳了
于是看T2，成功在拿到早餐前弄出来

于是我就很高兴地给帅爷爷发了个QQ
这里写图片描述
然而帅爷爷并没有看懂，然而我已经上课了。。
最后帅爷爷还是想了出来，好像意思是一样的

写详细点就是，你每遇到一个括号就跳到与他匹配的括号，然后扫的相反就好了，注意下细节。。~~并没有详细多少~~

其实一开始还想到有Splay，但是不想采用这个方法，据说会被卡掉

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>using namespace std;
const int Maxn=500010;
int tiao[Maxn];
char str[Maxn]; int num[Maxn]; stack<int>S; int N;int main()
{freopen("unknown.in","r",stdin);freopen("unknown.out","w",stdout);scanf("%s",str+1); N=strlen(str+1);int last=0;for(int i=1;i<=N;i++){if(str[i]=='(') last++;else if(str[i]==')')last--;num[i]=last; }for(int i=1;i<=N;i++){if(str[i]=='(') S.push(i);if(str[i]==')'){int x=S.top(); tiao[x]=i; tiao[i]=x;S.pop();}}int f=1; int p=1;while(p>=1 && p<=N){if(tiao[p]) p=tiao[p],f*=(-1);else printf("%c",str[p]);p+=f;}return 0;
}

T3

这题在下课的时候看了一下，没做出来
其实就是一个状压DP
f[i]表示这个状态下，最少需要多少组
0:这个人没有被分组 1:这个人已经有组了

然后枚举子集转移一下就好了，枚举子集是3^16次方的

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int Maxn=66000;
int bit[17]; int N,M,K; int F[Maxn];
bool bo[17][17];
int main()
{freopen("prison.in","r",stdin);freopen("prison.out","w",stdout);scanf("%d%d%d",&N,&M,&K); memset(bo,0,sizeof(bo));for(int i=1;i<=M;i++){int x,y; scanf("%d%d",&x,&y); x--; y--;bo[x][y]=bo[y][x]=1;}memset(F,63,sizeof(F));for(int i=0;i<(1<<N);i++){int s=0;for(int j=0;j<N;j++)for(int k=0;k<N;k++)if((i&(1<<j)) && (i&(1<<k)))if(bo[j][k]) s++;s/=2;if(s<=K) F[i]=1;for(int j=i;j;j=(j-1)&i)F[i]=min(F[i],F[j]+F[i^j]);}return printf("%d\n",F[(1<<N)-1]),0;
}

大概就这样吧，据说DAY2很水，大家都AK了，祝贺大家啊
~~不知道奖品什么时候到~~

金秋杯联赛模拟第一场（day2）

题解（伪）

T1

T2

T3