终于挽回了一点颜面。（模拟赛最水的一集）
排名
T1 打赌
不得语，暗相思，两心之外无人知。
一直记录这骰子的上面、正面和右面。先把暴力打出来，然后优化一下就行。同一行翻转的时候一直是四个状态循环，随便处理一下就行。
一顾倾城，再顾倾国。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
namespace Sub1{
void work(){
int up = 1,fr = 2,ri = 3,num = 1;
for(int i = 1;i <= n;i ++){
if(i % 2 == 1){
for(int j = 2;j <= m;j ++){
int nup = 7 - ri,nfr = fr,nri = up;
up = nup,fr = nfr,ri = nri,num += up;
}
int nup = 7 - fr,nfr = up,nri = ri;
up = nup,fr = nfr,ri = nri,num += up;
}
else{
for(int j = m - 1;j >= 1;j --){
int nup = ri,nfr = fr,nri = 7 - up;
up = nup,fr = nfr,ri = nri,num += up;
}
int nup = 7 - fr,nfr = up,nri = ri;
up = nup,fr = nfr,ri = nri,num += up;
}
}
printf("%lld",num - up);
}
}
namespace Sub2{
void work(){
int up = 1,fr = 2,ri = 3,num = 1;
for(int i = 1;i <= n;i ++){
if(i % 2 == 1){
int ans = up + ri + 7 - up + 7 - ri;
num += (m - 1) / 4 * ans;
for(int j = 1;j <= (m - 1) % 4;j ++){
int nup = 7 - ri,nfr = fr,nri = up;
up = nup,fr = nfr,ri = nri,num += up;
}
int nup = 7 - fr,nfr = up,nri = ri;
up = nup,fr = nfr,ri = nri,num += up;
}
else{
int ans = up + ri + 7 - up + 7 - ri;
num += (m - 1) / 4 * ans;
for(int j = 1;j <= (m - 1) % 4;j ++){
int nup = ri,nfr = fr,nri = 7 - up;
up = nup,fr = nfr,ri = nri,num += up;
}
int nup = 7 - fr,nfr = up,nri = ri;
up = nup,fr = nfr,ri = nri,num += up;
}
}
printf("%lld",num - up);
}
}
signed main(){
freopen("pogodak.in","r",stdin);
freopen("pogodak.out","w",stdout);
scanf("%lld%lld",&n,&m);
if(n <= 100 and m <= 100) Sub1::work();
else Sub2::work();
return 0;
}
T2 舞会
心不会动摇，动摇的是情。
对于喜欢比自己高的男孩和比喜欢比自己矮的女孩提取出来，分别按身高从小到大排序。每个男孩都尽量找离自己近的比自己高的女孩。正确性显然。其余同理。
琴与棋之中，涌动着相似的力量。
#include <bits/stdc++.h>
#define N 100005
using namespace std;
int n,a_z[N],a_f[N],b_z[N],b_f[N],num;
int cnt_a_z,cnt_a_f,cnt_b_z,cnt_b_f;
int main(){
freopen("party.in","r",stdin);
freopen("party.out","w",stdout);
scanf("%d",&n);
for(int i = 1,x;i <= n;i ++){
scanf("%d",&x);
if(x > 0) a_z[++cnt_a_z] = x;
else a_f[++cnt_a_f] = -x;
}
for(int i = 1,x;i <= n;i ++){
scanf("%d",&x);
if(x > 0) b_z[++cnt_b_z] = x;
else b_f[++cnt_b_f] = -x;
}
sort(a_z + 1,a_z + cnt_a_z + 1);
sort(a_f + 1,a_f + cnt_a_f + 1);
sort(b_z + 1,b_z + cnt_b_z + 1);
sort(b_f + 1,b_f + cnt_b_f + 1);
int j = 1;for(int i = 1;i <= cnt_a_z;i ++){
for(;j <= cnt_b_f;j ++){
if(a_z[i] < b_f[j]){num ++;break;}
}j ++;
}
j = 1;for(int i = 1;i <= cnt_b_z;i ++){
for(;j <= cnt_a_f;j ++){
if(b_z[i] < a_f[j]){num ++;break;}
}j ++;
}
printf("%d",num);
return 0;
}
T3 最小生成树
聆听渴望的，深信珍视的，沉醉梦寐以求的。
发现其实除 \(1\) 之外的所有数都向 \(1\) 连，这个时候所有的边权都是 \(1\)，是一个最小生成树。所以对于每一个点我们只能找比它小的且与它互质的数的个数，然后把它们乘起来就行了。注意模数非常的不正常。做法是欧拉函数。
情从何起，方能一往而深。
#include <bits/stdc++.h>
#define int long long
#define MOD 100000007
using namespace std;
int n,num = 1;
signed main(){
freopen("mst.in","r",stdin);
freopen("mst.out","w",stdout);
scanf("%lld",&n);
for(int i = 2;i <= n;i ++){
int ans = i,w = i;
for(int j = 2;j * j <= w;j ++){
if(w % j == 0){
ans = ans / j * (j - 1);
while(w % j == 0) w /= j;
}
}
if(w > 1) ans = ans / w * (w - 1);
num *= ans;num %= MOD;
}
printf("%lld",num);
return 0;
}
T4 买汽水
春江花月照人生无穷，弦音流转听山河入梦。
正解是考虑将汽水平均分成 \(2\) 组。每组 \(2^{n/2}\) 暴搜，每组至多 \(10^6\) 种情况。按价格排序。拿 \(2\) 个指针在 \(2\) 组扫，求最优值（注意常数）。
我是直接贪心加 shuffle 乱搞。
其实数据很水，前四个数据是所有的 \(a_i\) 相加，后六个是 \(m\)。
放的是我的贪心加 shuffle 乱搞代码。
最放不下的，终究是回忆吧。
#include <bits/stdc++.h>
#define N 45
using namespace std;
mt19937 rd(time(0));
int n,m,a[N],num;
namespace Sub1{
void dfs(int x,int sum){
num = max(num,sum);
if(x == n + 1) return ;
dfs(x + 1,sum);
if(sum + a[x] <= m) dfs(x + 1,sum + a[x]);
}
void work(){dfs(1,0);printf("%d",num);}
}
namespace Sub2{
void work(){
sort(a + 1,a + n + 1);
for(int i = 1;i <= n;i ++){
if(num + a[i] > m) break;
num += a[i];
}
while(double(clock()) / CLOCKS_PER_SEC < 1.9){
shuffle(a + 1,a + n + 1,rd);
int sum = 0,k = 0;
for(int i = 1;i <= n;i ++){
if(sum + a[i] > m) break;
k = i;sum += a[i];
}
num = max(num,sum);
for(int i = 1;i <= k;i ++){
for(int j = k + 1;j <= n;j ++){
if(sum - a[i] + a[j] <= m) num = max(num,sum - a[i] + a[j]);
}
}
if(num == m) break;
}
printf("%d",num);
}
}
int main(){
freopen("drink.in","r",stdin);
freopen("drink.out","w",stdout);
srand(time(0));
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i ++) scanf("%d",&a[i]);
if(n <= 20) Sub1::work();
else Sub2::work();
return 0;
}