第二届“清华社杯”大学生算法大赛个人题解
A题 变化的矩形
【题意】有一个面积为 S (1 < S < 1e9) 的矩形。在我们对其进行以下操作后，您必须算出它的新面积大小：
1、长度增加 50%
2、宽度减少 50%
#include <bits/stdc++.h>
using namespace std;
int main(){
int n; cin >>n;
long double ans = 0.75*n;
cout << fixed << setprecision(6) << ans;
return 0;
}
B题 吃鸡梦之队
【题意】有来自 4 台服务器的 N (4 ≤ N ≤ 1e5) 名吃鸡玩家，每名玩家只属于一台服务器。你知道每个玩家的技能值。现在上级命令你从每台服务器挑选一名玩家组建吃鸡梦之队。该队须满足以下两个条件：
设来自 1 号服务器的玩家的技能值为 X1 ，来自 2 号服务器的玩家的技能值为 X2 ,来自 3 号服务器的玩家的技能值为 X3 ，来自 4 号服务器的玩家的技能值为 X4 ，
组队条件是：
组建一只吃鸡梦之队，满足上述条件并且让 d (0 ≤ d) 的值尽可能小。
【思路】显然，必须要让 X1 和 X2 、X3 和 X4 尽可能接近是最优的。
我们先对这四类数进行排序。再不妨设X1<X2，通过枚举X1二分找到X2。再通过X1 - d ≤ X3 ≤X2 + d确定X3,X4即可。
#include <bits/stdc++.h>
#define endl '\n'
#define IO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
int a[100005];
inline void sol(){
vector<int> v[5]; int n; cin >> n;
for(int i=1;i<=n;i++) cin >> a[i];
for(int i=1;i<=n;i++){int x; cin>>x; v[a[i]].push_back(x);}
for(int i=1;i<=4;i++) sort(v[i].begin(),v[i].end());
int l=0, r=INT_MAX, ans=0;
while(l<=r){
int d = (l+r)>>1; bool flag=0;
for(auto &x1:v[1]){
auto pos = lower_bound(v[2].begin(),v[2].end(),x1);
if(pos==v[2].end()) break;
int x2 = *pos, delta = x2 - d;
pos = lower_bound(v[3].begin(),v[3].end(),delta);
if(pos==v[3].end()) continue;
int x3 = *pos;
pos = lower_bound(v[4].begin(),v[4].end(),delta);
if(pos==v[4].end()) continue;
int x4 = *pos;
if(max(x4,x3)<=x1+d){flag=1; break;}
}
for(auto &x2:v[2]){
auto pos = lower_bound(v[1].begin(),v[1].end(),x2);
if(pos==v[1].end()) break;
int x1 = *pos, delta = x1 - d;
pos = lower_bound(v[3].begin(),v[3].end(),delta);
if(pos==v[3].end()) continue;
int x3 = *pos;
pos = lower_bound(v[4].begin(),v[4].end(),delta);
if(pos==v[4].end()) continue;
int x4 = *pos;
if(max(x4,x3)<=x2+d){flag=1; break;}
}
flag ? ans=d, r=d-1 : l=d+1;
}
cout << ans << endl;
}
int main(){
IO; int ttt; cin >> ttt;
while(ttt--) sol(); return 0;
}
C题 洞穴探险
【题意】N个点， M 条通路，Q 次询问，第 i 个问题是点 Xi 和点 Yi 之间有没有路径，必须告诉回答没有路径（NONE）、一条路径(ONE)或存在多条路径(MORE THAN ONE)。注意，路径不应多次通过同一个小洞，也不应多次通过同一条隧道。
【思路】以下代码应该是WA + TLE了，回头看看能不能补题，要解决这个数据量的无向图连接问题，应该是要用上并查集(？)
#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define ll long long
#define endl '\n'
using namespace std;
class Graph {
public:
Graph(int n) : N(n), adj(n) {}
void addEdge(int x, int y) {
adj[x].push_back(y);
adj[y].push_back(x);
}
// 深度优先搜索，用于查找从x到y是否有路径
bool dfs(int start, int target, vector<bool>& visited) {
if (start == target) return true;
visited[start] = true;
for (int node : adj[start]) {
if (!visited[node]) {
if (dfs(node, target, visited)) return true;
}
}
return false;
}
string ans(int Xi, int Yi) {
vector<bool> visited(N, false);
// 初始调用DFS
bool hasPath = dfs(Xi, Yi, visited);
if(!hasPath) return "NONE";
else {
fill(visited.begin(), visited.end(), false);
adj[Yi].erase(remove(adj[Yi].begin(), adj[Yi].end(), Xi), adj[Yi].end());
adj[Xi].erase(remove(adj[Xi].begin(), adj[Xi].end(), Yi), adj[Xi].end());
if(dfs(Xi, Yi, visited)) return "MORE THAN ONE";
else return "ONE";
}
}
private:
int N;
vector<vector<int>> adj;
};
int main() {
IO; int n, m, q; cin >> n >> m >> q;
Graph g(n);
for(int i=0;i<m;i++) {
int x, y; cin >> x >> y;
g.addEdge(x,y);
}
for(int i=0;i<q;i++) {
int x, y; cin >> x >> y;
cout << g.ans(x,y) << endl;
}
return 0;
}
D题 火柴棒等式
【题意】这是一个由火柴棒组成的等式（如: 9 - 1 = 4），但它可能不正确。我们需要找到使等式正确所需的最少移动次数（如果没有的话输出-1）。
【思路】枚举，等式由“数字-符号-数字-等于号-数字”组成，所以总情况数为10*2*10*10=2000种。在考虑每个数字最多由7根火柴棒组成，考虑用二进制01串来表述
#include <bits/stdc++.h>
#define ll long long
using namespace std;
map<ll, bool> mp;
// <<0表示上边 <<1表示右上边 <<2表示右下边 <<3表示下边
// <<4表示左下边 <<5表示左上边 <<6表示中边
const int num[10] = {//分别为0~9
(1 << 0)+(1 << 1)+(1 << 2)+(1 << 3)+(1 << 4)+(1 << 5),
(1 << 1)+(1 << 2),
(1 << 0)+(1 << 1)+(1 << 3)+(1 << 4)+(1 << 6),
(1 << 0)+(1 << 1)+(1 << 2)+(1 << 3)+(1 << 6),
(1 << 1)+(1 << 2)+(1 << 5)+(1 << 6),
(1 << 0)+(1 << 2)+(1 << 3)+(1 << 5)+(1 << 6),
(1 << 0)+(1 << 6)+(1 << 2)+(1 << 3)+ (1 << 4)+(1 << 5),
(1 << 0)+(1 << 1)+(1 << 2),
(1 << 0)+(1 << 1)+(1 << 2)+(1 << 3)+(1 << 4)+(1 << 5)+(1 << 6),
(1 << 0)+(1 << 1)+(1 << 2)+(1 << 3)+(1 << 5)+(1 << 6)
};
ll trans(int a, int op, int b, int c){
ll encoder = 0;
encoder += num[a]; encoder <<= 7;
encoder += num[b]; encoder <<= 7;
encoder += num[c]; encoder <<= 2;
if(op==2) return encoder+=3;//(11)2
else return encoder+=2; //(10)2
}
void init(){
for(int x1=0;x1<10;x1++)
for(int x2=0;x2<10;x2++)
for(int x3=0;x3<10;x3++)
for(int op=1;op<=2;op++)
if((op==1 && x1-x2==x3)||(op==2 && x1+x2==x3))
mp[trans(x1,op,x2,x3)]=1;
}
inline void sol(){
int a, b, c, op, ans = 999999;
char ch, useles;
cin >> a >> ch >> b >> useles >> c;
op = ch=='+'?2:1;
ll now = trans(a,op,b,c), cnt1 = __builtin_popcount(now);
for(auto &x:mp){
ll tmp = x.first;
if(__builtin_popcount(tmp)!=cnt1) continue;
int cnt = 0;
for(int i=0;i<30;i++){
if(((now>>i)&1)!=((tmp>>i)&1)) ++cnt;
ans=min(ans,cnt/2);
}
if(ans==999999) puts("-1");
else cout << ans << endl;
}
int main(){
int ttt; cin >> ttt; init();
while (ttt--) sol();
return 0;
}
E题 排序
【题意】构造一个排列，使得每两个连续数字之间的绝对差的总和 f(p) 最大。如n=5时，排列 4 1 5 2 3 的可取到 f(p) 最大值11。
【思路】贪心，最大最小的数先放一起，让后用双端数组看看是放左边收益大还是右边收益大，最后求和 f(p) 即可。
#include <bits/stdc++.h>
#define ll long long
#define IO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const int N =1e5+5;
int a[N],q[N];
void sol(){
int n; ll sum=0;
deque<int> a; cin >> n;
a.push_back(1),a.push_back(n);
sum+=abs(n-1);
int p1=1,p2=n,cnt=0;
while(p1!=p2){
++cnt;int i;
if(cnt&1) i=(++p1);
else i=(--p2);
if(p1==p2) break;
if(abs(i-a.back())>abs(i-a.front()))
sum+=abs(i-a.back()),a.push_back(i);
else sum+=abs(i-a.front()),a.push_front(i);
}
cout <<sum << "\n";
}
int main(){
IO; int ttt; cin >>ttt;
while(ttt--) sol();
return 0;
}
F题 数组查询
【题意】给定一个数组，第i次查询时给一个数Xi，并询问数组前i个元素中小于等于Xi的最大元素。
【思路】采用multiset模拟，STL中set容器的upper_bound(k)函数可以返回一个指向键k之后下一个元素的迭代器。
#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define ll long long
const int N = 1e5+5;
using namespace std;
ll a[N];
inline void sol(){
int n; cin>>n;
for(int i=1;i<=n;i++) cin >> a[i];
multiset<int> s;
for(int i=1;i<=n;i++){
int x; cin >> x;
s.insert(a[i]);
auto it = s.upper_bound(x);
if(it==s.begin()) puts("-1");
else cout << *(--it) << endl;
}
}
int main(){
IO; int ttt; cin >> ttt;
while(ttt--) sol();
return 0;
}
G题 新冠病毒
【题意】已知第i天新增i个病例，计算n天内的感染总数和平均感染数。
#include <bits/stdc++.h>
#define ll long long
int main(){
ll n; std::cin >> n;
std::cout << n*(n+1)/2 << '\n' << (n+1)/2;
return 0;
}
H题 有星星就表白
【题意】每次给定一个由 N 个顶点和 M 条边组成的连通无向图（不包含自环或重边），如果是菊花图则输出Yes，否则输出No。
【思路】显然只能有n-1条边，图要联通。然后一个点作为中心，因此只有一个点的度数可以大于2。就做完了。
#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define ll long long
using namespace std;
const int N =1e5+5;
ll a[N],f[N];
int find(int x){
return f[x]==x ? x : f[x]=find(f[x]);
}
inline void sol(){
int n, m; cin >> n >> m;
for(int i=1;i<=n;i++) f[i]=i,a[i]=0;
bool flag=1; int cnt=0;
for(int i=1;i<=m;i++){
int x, y; cin >> x >> y;
++a[x], ++a[y];
int fx = find(x), fy=find(y); f[fx]=fy;
if(fx==fy) flag=0;
}
if(m+1!=n||!flag){puts("No"); return ;}
for(int i=1;i<=n;i++)
if(a[i]>2) cnt++;
if(cnt<=1) puts("Yes");
else puts("No");
}
int main(){
IO; int ttt; cin >> ttt;
while(ttt--) sol();
return 0;
}
I题 笑声比赛
【题意】给定一长度为n的字符串，询问m次，每次询问给出两个字符X和Y和一个长度L，问以XY结尾且长度为L的子序列共有多少个，结果对1e9+7取模。
【思路】动态规划，取字符串最后出现的XY，往前寻找长度为 len - 2 的子序列，用last记录上一个a[i]位置，则状态转移方程如下：（不要忘记取模技巧~）
1、如果last[a[i]] = 0, f[i][j] = f[i-1][j] + f[i-1][j-1]；
2、否则f[i][j] = f[i-1][j] + f[i-1][j-1] - f[last[a[i]] - 1][j-1]
#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define ll long long
using namespace std;
const ll N=1e3+5, mod=1e9+7;
ll f[N][N]={{0}}, last[N], pos[27];
inline void sol(){
int n; cin >> n;
string s; cin >> s;
int siz = s.size();
memset(pos,0,sizeof pos); memset(f,0,sizeof f);
for(int i = 0; i < siz; i++)
last[i+1]=pos[s[i]-97], pos[s[i]-97]=i+1;
f[0][0]=1;
for(int i=1;i<=n;i++){
f[i][0]=1;
for(int j=1;j<=i;j++){
f[i][j]=(f[i-1][j]+f[i-1][j-1])%mod;
if(last[i]!=0) f[i][j]=(f[i][j]-f[last[i]-1][j-1]+mod)%mod;
}
}
int q; cin >> q;
while(q--){
char x, y; cin >> x >> y;
int len; cin >> len;
size_t tmp = s.rfind(y);
tmp = s.rfind(x,tmp);
if((int)tmp<len-2){cout << "0\n"; continue;}
else cout << f[tmp][len-2]%mod << endl;
}
}
int main(){
IO; int ttt; cin >> ttt;
while(ttt--) sol();
return 0;
}
J题 行走之谜
【题意】没看懂，放一下原题，估计是不会补了。
