两场比赛，一个50，一个爆零
叉叉计算
先扫一遍找区间，然后排序判断即可，考试跳过，0分
#include <bits/stdc++.h>
using namespace std;
struct letter {
int x, y;
bool operator<(const letter &a) const { return x < a.x; }
} let[100002];
string s;
int ans = 0, vis[28], p = 1;
int main() {
freopen("cross.in", "r", stdin);
freopen("cross.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> s;
memset(vis, -1, sizeof(vis));
for (int i = 0; i < s.size(); i++) {
if (vis[s[i] - 'a'] == -1) {
vis[s[i] - 'a'] = i;
} else {
let[p].x = vis[s[i] - 'a'];
let[p].y = i;
p++;
vis[s[i] - 'a'] = -1;
}
}
sort(let + 1, let + p);
for (int i = 1; i < p; i++) {
for (int j = i + 1; j < p; j++) {
if (let[j].x >= let[i].y) {
break;
} else {
if (let[j].y > let[i].y) {
ans++;
}
}
}
}
cout << ans;
return 0;
}
病毒分裂
我不会！我不会！我不会！啊！！！！
考试的时候快速幂，50分
完了之后去找yy学矩阵乘法，还是不会
50分代码还找不到了（恼
慢跑问题
考试RE爆零，但是int和bool都有返回值
我以为2000K的内存太大，然而xkr过来把我的10w数组改为1000w就不会RE了
（此时的内存是80000K+）
具体原理我也不懂，然后自己手搓的代码还只有40
正解用vector，然而不会
附40分代码
#include<bits/stdc++.h>
using namespace std;
#define inf 202309300
struct road{
int u,v,cost;
}a[100005];
int n,ml,md,dp[100005];
bool cmp(road a,road b){
return a.u<b.u;
}
int main(){
freopen("jogging.in","r",stdin);
freopen("jogging.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>ml>>md;
for(int i=1;i<=100005;i++){
dp[i]=inf;
}
for(int i=1;i<=ml;i++){
cin>>a[i].u>>a[i].v>>a[i].cost;
if(a[i].u>a[i].v){
swap(a[i].u,a[i].v);
}
}
int m=ml+md;
for(int i=ml+1;i<=m;i++){
int c;
cin>>a[i].u>>a[i].v;
if(a[i].u>a[i].v){
swap(a[i].u,a[i].v);
}
cin>>c;
a[i].cost=-c;
}
sort(a+1,a+m+1,cmp);
dp[1]=0;
for(int i=1;i<=m;i++){
if(dp[a[i].u]!=inf){
dp[a[i].v]=min(dp[a[i].u]+a[i].cost,dp[a[i].v]);
}
else{
int p=1;
while(dp[a[i].u]==inf&&p<=m-i){
swap(a[i].u,a[i+p].u);
swap(a[i].v,a[i+p].v);
swap(a[i].cost,a[i+p].cost);
p++;
}
}
}
cout<<dp[n]<<endl;
if(dp[n]<0){
cout<<"YES";
}
else{
cout<<"NO";
}
return 0;
}
100分代码
#include <bits/stdc++.h>
using namespace std;
int n, m1, m2, f[1000001];
vector<int> to[1000001][2];
int main() {
freopen("jogging.in", "r", stdin);
freopen("jogging.out", "w", stdout);
cin>>n>>m1>>m2;
int a,b,c;
for (int i=1;i<=m1;++i) {
scanf("%d%d%d",&a,&b,&c);
if (a>b)
swap(a,b);
to[b][0].push_back(a),to[b][1].push_back(c);
}
for (int i = 1; i <= m2; ++i) {
scanf("%d%d%d",&a,&b,&c);
if (a>b)
swap(a,b);
to[b][0].push_back(a),to[b][1].push_back(-c);
}
for (int i = 2; i <= n; ++i) {
f[i] = 1e9;
for (int j = 0; j < to[i][0].size(); ++j) f[i] = min(f[i], f[to[i][0][j]] + to[i][1][j]);
}
cout << f[n] << endl;
if (f[n] < 0)
cout << "YES";
else
cout << "NO";
return 0;
}
距离之美
过！
最短路上
Floyd秒了，有什么好说的
然而考试的时候不会Floyd，裂
改后AC代码
#include<bits/stdc++.h>
using namespace std;
int g[114][114],n,m,t;
int main(){
freopen("count.in","r",stdin);
freopen("count.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
memset(g,0x3f,sizeof(g));
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
g[v][u]=g[u][v]=min(g[u][v],1);
}
for(int i=1;i<=n;i++){
g[i][i]=0;
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(g[i][j]>=g[i][k]+g[k][j]){
g[i][j]=g[i][k]+g[k][j];
}
}
}
}
cin>>t;
int ans;
for(int i=1;i<=t;i++){
ans=0;
int x,y;
cin>>x>>y;
for(int i=1;i<=n;i++){
if(g[x][y]==g[x][i]+g[i][y]){
ans++;
}
}
cout<<ans<<endl;
}
return 0;
}
古老谜题
53分代码
#include<bits/stdc++.h>
using namespace std;
int n,idx,cs,num,ans;
string s;
int Num[1000002][2];
signed main()
{
freopen("puzzle.in", "r", stdin);
freopen("puzzle.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>idx>>n>>s;
for(int i=1;i<=n;i++){
if(s[i-1]=='1'){
num++;
}
Num[i][0]=Num[i-1][0];
Num[i][1]=Num[i-1][1];
Num[i][num&1]++;
}
cs=num;num=0;
for(int i=1;i<=n;i++){
if(s[i-1]=='1'){
if(num!=0){
ans+=Num[n][num&1]-Num[i][num&1];
}
num++;
continue;
}
ans+=Num[n][(num+1)&1]-Num[i][(num+1)&1]-(num<cs?1:0);
}
cout<<ans;
return 0;
}
100分代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
char c[1000001];
int Num[1000001][2];
signed main()
{
freopen("puzzle.in", "r", stdin);
freopen("puzzle.out", "w", stdout);
int idx;
scanf("%lld", &idx);
int num = 0;
int ans = 0;
scanf("%lld", &n);
scanf("%s", c);
//前缀和处理
for(int i = 1; i <= n; i++)
{
if(c[i - 1] == '1')
num++;
Num[i][0] = Num[i - 1][0];
Num[i][1] = Num[i - 1][1];
Num[i][num & 1]++;
}
int hhh = num;
num = 0;
for(int i = 1; i <= n; i++)
{
if(c[i - 1] == '1')
{
//计算上一个1的答案
if(num != 0) ans += Num[n][num & 1] - Num[i][num & 1];
num++;
continue;
}
//计算0的答案
ans += Num[n][(num + 1) & 1] - Num[i][(num + 1) & 1] - (num < hhh ? 1 : 0);
}
printf("%lld", ans);
return 0;
}
礼物购买
考试时递归炸了，正解二分
货运公司
倍增
退！退！退！
总结
……
第一天不应该，不应该看题目比较复杂就跳过
第二天更不应该，回去手搓Floyd！
……
已经结束咧！
伥伥伥伥伥伥伥