今日头条杯2018湖北省大学生程序设计竞赛（网络赛）The 2018 Hubei Collegiage Programming Contest Online
蒟蒻打的是网络赛，讲道理会比WHU现场的朋友们轻松很多，然而，各种小错误不断，G交互题各种wa，赛后补题才发现自己多了一个scanf，
已被队友锤爆（倒地）
行啦，现在来个伪全题解
PROBLEM A
A. GSS and CQ
这题就是一个模拟change一下就好啦，出题组给了文本很良心！
PROBLEM B
B. GSS and Interesting Sculpture
这题比赛是疯狂wa……一共wa了5发…..又被队友锤爆……
这题算一下被截取部分的曲面积分然后再减掉就好啦，我自己wa5遍的地方是判断相交截取部分要以圆心和两个交点是否能构成三角形的极限位置为边界区分两种情况，zz的me直接以Max(R,r)当作边界了……
PROBLEM C
C. GSS and Bubble Sort
这题拿到题我们可以很容易发现他的ans与全排列有关系，那么多半是个打表找规律的题目，通过打表我们可以相对容易的发现ans就是(n−1)∗n/4，在这里我们以可以发现一个很有趣的事，这个ans其实相当于n∗(n−1)/2/2，就是最大比较次数除2
PROBLEM D
D. GSS and Version Control
水题，过
PROBLEM E
E. Jump A Jump
这题赛时是队友在写，不过当时自己的想法是对bi取模后再完全背包，感觉似乎可行，但没继续想下去就滚去写别的了。
赛后和队友讨论以及看省赛群里dalao的解法发现自己的思考方向其实并没有错，只不过我这个完全背包似乎有点尴尬……
队友的想法是取bi中的最小值然后取模之后k∗bi都可以表示出来，那么便可以转化为最短路问题了。
#include<cstdio>
#include<iomanip>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<vector>
#include<set>
#include<queue>
#include<limits.h>
#include<string.h>
#include<map>
#include<list>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf int(0x3f3f3f3f)
#define mod int(1e9+7)
#define eps double(1e-6)
#define pi acos(-1.0)
#define lson root << 1
#define rson root << 1 | 1
typedef pair<int,int>pii;
priority_queue<pii>pq;
ll n,m;
int mi[5005][5005];
int d[5005];
int b[2005];
void init()
{
memset(mi,-1,sizeof(mi));
memset(d,-1,sizeof(d));
d[0]=0;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
init();
cin>>n>>m;
for(int i=1;i<=m;i++)
cin>>b[i];
sort(b+1,b+1+m);
for(int i=0;i<b[1];i++)
mi[i][i]=0;
for(int i=0;i<b[1];i++)
{
for(int j=1;j<=m;j++)
{
if(mi[i][(i+b[j])%b[1]]==-1)
mi[i][(i+b[j])%b[1]]=(i+b[j])/b[1];
else
mi[i][(i+b[j])%b[1]]=min((i+b[j])%b[1],(i+b[j])/b[1]);
}
}
pq.push({0,0});
while(!pq.empty())
{
int dis=pq.top().first;
int u=pq.top().second;
pq.pop();
if(dis>d[u])
continue;
for(int i=0;i<b[1];i++)
{
if(mi[u][i]==-1)
continue;
if(d[i]==-1||d[u]+mi[u][i]<d[i])
{
d[i]=d[u]+mi[u][i];
pq.push({d[i],i});
}
}
}
ll sum=n;
for(int i=0;i<b[1];i++)
{
if(d[i]==-1)
continue;
if(d[i]*b[1]+i<=n)
{
sum=min(sum,min(n-(n-i)/b[1]*b[1]-i,(n+b[1]-i)/b[1]*b[1]+i-n));
}
else
sum=min(sum,d[i]*b[1]+i-n);
}
cout<<sum<<"\n";
}
PROBLEM
F A-maze-ing
裸题，模板copy（vegetable）
强连通缩点后求DAG最长链
#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
using namespace std;
#define _clr(x, y) memset(x, y, sizeof (x))
#define Min(x, y) (x < y ? x : y)
#define Max(x, y) (x > y ? x : y)
#define INF 0x3f3f3f3f
#define N 200010
vector<int> map[N], new_map[N];
int low[N], dfn[N];
int Stack[N], be[N];
bool instack[N];
int dist[N], sum[N];
int top, n, cnt, Time;
void Init()
{
top = Time = cnt = 0;
_clr(instack, 0);
_clr(Stack, 0);
_clr(dist, -1);
_clr(low, 0);
_clr(sum, 0);
_clr(dfn, 0);
_clr(be, 0);
for(int i=0; i<=n; i++)
{
map[i].clear();
new_map[i].clear();
}
}
void dfs(int u)
{
dfn[u] = low[u] = ++Time;
Stack[top++] = u;
instack[u] = true;
for(int i=0; i<(int)map[u].size(); i++)
{
int v = map[u][i];
if(!dfn[v])
{
dfs(v);
low[u] = Min(low[u], low[v]);
}
else if(instack[v])
low[u] = Min(low[u], dfn[v]);
}
if(dfn[u]==low[u])
{
cnt++;
do
{
u = Stack[--top];
instack[u] = false;
be[u] = cnt;
sum[cnt]++;
}while(dfn[u] != low[u]);
}
}
void Tarjan_Scc()
{
for(int i=1; i<=n; i++)
{
if(!dfn[i])
dfs(i);
}
for(int i=1; i<=n; i++)
{
for(int j=0; j<(int)map[i].size(); j++)
{
int v = map[i][j];
if(be[i] != be[v])
new_map[be[i]].push_back(be[v]);
}
}
}
int Get(int u)
{
if(dist[u]!=-1) return dist[u];
dist[u] = 0;
for(int i=0; i<(int)new_map[u].size(); i++)
dist[u] = Max(Get(new_map[u][i]), dist[u]);
return dist[u] = dist[u] + sum[u];
}
int main()
{
int m, x, y;
while(~scanf("%d%d",&n,&m))
{
Init();
for(int i=0; i<m; i++)
{
scanf("%d%d",&x, &y);
map[x].push_back(y);
}
Tarjan_Scc();
int ans = -INF;
for(int i=1; i<=cnt; i++)
ans = Max(Get(i), ans);
printf("%d\n", ans);
}
return 0;
}
PROBLEM G
G.Pretty Derby
这明显是一道思维题，解法很简单，一共25匹马，前五次找出每次比赛中first和second速度的马，第六次在五个first中找到的fatest即是最快的马，第七次在剩下的马中找到的最快的马就是速度第二的马。
#include<cstdio>
#include<iomanip>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<vector>
#include<set>
#include<queue>
#include<limits.h>
#include<string.h>
#include<map>
#include<list>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf int(0x3f3f3f3f)
#define mod int(1e9+7)
#define eps double(1e-6)
#define pi acos(-1.0)
#define lson root << 1
#define rson root << 1 | 1
using namespace std;
typedef long long ll;
int rk[30][30];
int shu[10];
int fst;
int snd;
int main()
{
for(int i=0; i<5; i++)
shu[i]=i+1;
for(int i=0; i<5; i++)
cout<<shu[i]<<" ";
cout<<endl;
cout.flush();
for(int i=0; i<5; i++)
{
for(int j=0; j<5; j++)
{
int num;
cin>>num;
rk[i][num-1]=shu[j];
if(i<4)
{
shu[j]+=5;
cout<<shu[j]<<" ";
}
}
if(i!=4)
cout<<endl;
}
for(int k=0;k<5;k++)
cout<<rk[k][0]<<" ";
cout<<endl;
cout.flush();
for(int i=0; i<5; i++)
{
int num;
cin>>num;
if(num==1)
{
fst=rk[i][0];
swap(rk[i][0],rk[i][1]);
}
cout<<rk[i][0]<<" ";
}
cout<<endl;
cout.flush();
for(int i=0; i<5; i++)
{
int num;
cin>>num;
if(num==1)
snd=rk[i][0];
}
cout<<fst<<" "<<snd<<" 0 0 0"<<endl;
}
PROBLEM H
H. GSS and OJ Submissions
这题第一眼看上去很简单，是找第k大，但是n最大4e8，一般的直接找肯定不行了，全部存下开也会爆内存。
二分的话nlogn，光是一个n就要1s了，再乘一个常数肯定要爆炸。
那，分块暴力就完事了.
#include<cstdio>
#include<iomanip>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<vector>
#include<set>
#include<queue>
#include<limits.h>
#include<string.h>
#include<map>
#include<list>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf int(0x3f3f3f3f)
#define mod int(1e9+7)
#define eps double(1e-6)
#define pi acos(-1.0)
#define lson root << 1
#define rson root << 1 | 1
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
vector<ull>vec;
int blocks[1000000];
ull A,B,L,n,s0;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>A>>B>>L>>n>>s0;
ull now=s0;
for(ull i=1; i<=n; i++)blocks[now/(((ull)-1ll)/100000ull)]++,now=now*A+B;
ull pos,sum=0;
for(pos=0; pos<1000000; pos++)
{
sum+=blocks[pos];
if(sum>=L)break;
}
now=s0;
for(ull i=1; i<=n; i++)
{
if(now/(((ull)-1ll)/100000ull)==pos)vec.push_back(now);
now=now*A+B;
}
sort(vec.begin(),vec.end());
sum-=blocks[pos];
L-=sum;
cout<<vec[L-1]<<endl;
}
发表评论