头像

tomousw




离线:4小时前


最近来访(79)
用户头像
程点
用户头像
王海宇
用户头像
辣鸡号航母
用户头像
hpstory
用户头像
_Hzj
用户头像
用户头像
小姜莱
用户头像
稚宇
用户头像
Falchion_5
用户头像
Lance_2
用户头像
Moyou
用户头像
cbatea
用户头像
tyjz_yyds
用户头像
fangzichang
用户头像
向小铭
用户头像
HfjNUlYZ
用户头像
牧濑红莉栖
用户头像
MiuSe
用户头像
大智慧的益生菌
用户头像
yxc的小迷妹


tomousw
6天前

广义鸽巢原理: 把(mn-1)个物体放入n个抽屉中,其中必有一个抽屉中至多有(m—1)个物体。
错误证明:
假设不存在抽屉中至多有(m-1)个物体
即所有抽屉,每个抽屉物体数都大于m-1
那么物体总数大于mn-n
被卡住
因为这样推不出矛盾
改成如下证明:
假设不存在抽屉中至多有(m—1)个物体
即所有抽屉,每个抽屉物体数都大于m-1,即大于等于m
那么物体总数大于等于mn
推出了矛盾
由此可见离散数学中由个体满足的性质拓展到整体时,x>=y和x>y-1不能当作等价的v条件
因为两边乘以倍数后容易放缩过度,而转换为含有大(小)于等于的式子放缩更精密,不容易放缩过度

上面问题是学习P180.排书的上下取整恒等式时发现的
参考链接,留待日后学习
先记住结论:
8.jpg




tomousw
20天前
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int pow10(int x){
    int res=1;
    while(x--)res=res*10;
    return res;
}
//注意t==0时前导零的影响
//注意从次高位开始,高位就一定不是全0
int count(int n,int t){//返回1~n各数中含有t的个数
    if(n==0)return 0;
    vector<int> num;
    while(n){
        num.push_back(n%10);
        n/=10;
    }
    int last=0;//为i位以前各位中t的个数
    int res=0;
    for(int i=num.size()-1;i>=0;i--){
        int x=num[i];
        for(int j=0;j<x;j++){//左分支
            bool cmp=j==t;//第i位和t是否相等
            if(t>0 || t==0 && i<num.size()-1)res+=(last+cmp)*pow10(i);//加上已经确定位的各数的贡献
            //考虑t==0且最高位左分支为0时不能添加该贡献,因为那个0根本不存在
            if(i>0){//除去大小限制后 后i位 各位的贡献值
                if(t==0 && i==num.size()-1 && j==0){
                //t==0时考虑最高位的左分支时,注意做贡献的那一位的左边各位不能全为0
                    for(int k=1;k<=i;k++){//k为贡献位所在位置
                        res+=pow10(i-1)-pow10(i-k);//贡献位外随便选的数字数 减去 贡献位左边全选0的数字数
                    }
                }
                else res+=i*pow10(i-1);
            }
        }
        if(i==0)res+=last+(x==t);//加上最终右分支的那个所有位都确定的数的贡献值
        last+=(x==t);//更新记录last(不用特判因为首位一定非0)
    }
    return res;
}

int main(){
    int a,b;
    while(cin>>a>>b,a && b){
        if(a>b)swap(a,b);
        for(int i=0;i<=9;i++){
            cout<<count(b,i)-count(a-1,i)<<' ';
        }
        cout<<endl;
    }
    return 0;
}



tomousw
22天前

代码本身应该是有问题的,第一次调用应该是没有返回值的
但是不知道为什么返回了第二次调用返回的结果

// #pragma GCC optimize(2)
#include <iostream>
using namespace std;

int a;

int f(){
    if(a>0)return 999;
    a++;
    f();
}

int main(){
    cout<<f();
    return 0;
}

运行结果:

999

如果开O2优化,则会SF




tomousw
1个月前

d.jpg

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
//#define ll __int128
#define speed_up ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
//speed_up只能放在主函数内最前面

const int N=1010;
int n,m,c,idx;
int e[N],ne[N],h[N];
int v[N];//过路费
int w[N];//限制重量
bool st[N];
int dist[N];

void add(int a,int b,int ww,int vv){
    e[idx]=b,w[idx]=ww,v[idx]=vv,ne[idx]=h[a],h[a]=idx++;
}

bool dijk(int ww){
    priority_queue<pii,vector<pii>,greater<pii>>q;
    q.push({0,1});
    dist[1]=0;
    while(q.size()){
        auto t=q.top();
        q.pop();
        int ver=t.second;
        if(st[ver])continue;
        st[ver]=true;
        for(int i=h[ver];~i;i=ne[i]){
            int j=e[i];
            if(w[i]<ww)continue;
            if(c-dist[ver]<v[i])continue;
            if(dist[j]>dist[ver]+v[i]){
                dist[j]=dist[ver]+v[i];
                q.push({dist[j],j});
            }
        }
    }
    return dist[n]<=c;
}

int main(){
    speed_up;
   cin>>n>>m>>c;
   memset(h,-1,sizeof h);
   for(int i=0;i<m;i++){
       int x,y,ww,vv;
       cin>>x>>y>>ww>>vv;
       add(x,y,ww,vv),add(y,x,ww,vv);
   }
   for(int i=100;i>=0;i--){
       memset(st,0,sizeof st);
       memset(dist,0x3f,sizeof dist);
       if(dijk(i)){
           cout<<i;
           return 0;
       }
   }
}

这种比赛居然还出图论题
没复习图论的下场
我居然还调了半小时
可太没经验了
这个题显然可以调大数据范围,还可以考个二分什么的




tomousw
1个月前

[传智杯 #5 初赛] D-莲子的物理热力学

题目背景

莲子正在研究分子的运动。

每个分子都有一个速度,约定正方向为正,负方向为负。分子的数量极多,速度又并不一致,看上去杂乱无章。于是莲子希望调整部分分子的速度,使得最终分子们看上去整齐。

题目描述

莲子给定了 $n$ 个整数 $a_1,a_2,\cdots a_n$,描述每个分子。现在她可以进行至多 $m$ 次操作(也可以一次也不进行),每次操作可以执行以下两条之一:

  • 选择 $i$,满足 $a_i=\min_j{a_j}$,然后将 $a_i$ 变为 $\max_j{a_j}$。
  • 选择 $i$,满足 $a_i=\max_j{a_j}$,然后将 $a_i$ 变为 $\min_j{a_j}$。

现在莲子希望需要最小化最终序列的极差(最大值减去最小值的差)。请求出最小的极差。


例如,对于序列 $a={5,1,4}$,可以进行如下几次操作:

  • 选择 $i=1$,满足 $a_1=5$ 是当前的最大值 $5$,可以将 $a_1$ 修改成当前的最小值 $1$,此时序列变成 ${1,1,4}$;
  • 再选 $i=2$,满足 $a_2=1$ 是当前的最小值 $1$,可以将 $a_2$ 修改成当前的最大值 $4$,此时序列变成 ${1,4,4}$。

这两次操作后得到的序列为 ${1,4,4}$。最大值减去最小值的差为 $|4-1|=3$。

当然,这种操作方式得到的极差并非最小。最优策略是,先将最大值 $a_1=5$ 变成目前的最小值 $1$,再把此时的最大值 $a_3=4$ 变成目前的最小值 $1$。此时序列为 ${1,1,1}$,得到的极差 $|1-1|=0$ 是所有策略中最小的。

输入格式

  • 第一行有两个正整数 $n,m$,分别表示序列的长度和你最多可以进行的操作次数。
  • 第二行有 $n$ 个整数 $a$,描述给定的序列。

输出格式

  • 输出共一行一个整数,表示最优策略下能得到的最小极差。

样例 #1

样例输入 #1

3 2
5 1 4

样例输出 #1

0

样例 #2

样例输入 #2

8 0
1 2 3 4 5 6 7 8

样例输出 #2

7

样例 #3

样例输入 #3

8 3
1 5 5 5 6 6 9 10

样例输出 #3

4

提示

样例解释

样例 $1$:${5,1,4}\to{1,1,4}\to{1,1,1}$,极差为 $0$。
样例 $2$:${1,2,3,4,5,6,7,8}$,什么也做不了,极差为 $7$。
样例 $3$:${1,5,5,5,6,6,9,10}\to{10,5,5,5,6,6,9,10}\to{5,5,5,5,6,6,9,10}\to{5,5,5,5,6,6,9,5}$,极差为 $4$。

数据范围及约定

对于全部数据,保证 $1\le n \le 10^5$,$0\le m\le10^9$,$|a_i|\le 10^9$。

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
//#define ll __int128
#define speed_up ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
//speed_up只能放在主函数内最前面

const int N=1e5+10;
int n,m;
int a[N];

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+n+1);
    if(m>=n-1){
        cout<<0;
        return 0;
    }
    int l=1,r=1;
    int ans=2e9;
    for(;l<=n && l<=m+1;l++){
        if(r<l)r=l;
        while(l-1+n-r+min(l-1,n-r)>m)r++;
        if(r>n)break;
        ans=min(ans,a[r]-a[l]);
    }
    cout<<ans;
    return 0;
}

感受

题解看老半天才懂
一心想着怎么优化模拟,一看正解,完全不在一个层次hh
应该着眼于最终变换后区间的情况,模拟思路发现行不通就应该放弃了
下面开始描述正解
首先是一个神秘结论,倒是很好证明
把[1,n]区间的数按照操作放进[l,r]区间至少需要操作步数是

l-1+n-r+min(l-1,n-r)

证明大概是只有一边没有数的时候才能移进区间里,全移动到一边需要min(l-1,n-r)
再都移动到区间里需要l-1+n-r
就没了
然后尝试枚举区间[l,r]求极差最小值
表面是n^2复杂度
但是可以发现满足双指针性质(满足条件最优的j随i增加只增不减)
然后就是几个细节(坑)
最大的一个就是0x3f3f3f3f不够打,是稍稍比1e9大的数
然后就是r不能比l小
突然想起来那个A题,int正数最大值的相反数会越界
很细很坑
大概看了眼另一种思路,码了下代码尝试,居然顺利过了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
//#define ll __int128
#define speed_up ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
//speed_up只能放在主函数内最前面

const int N=1e5+10;
int n,m;
int a[N];

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+n+1);
    if(m>=n-1){
        cout<<0;
        return 0;
    }
    int ans=2e9;
    for(int i=max(1,m-n+2);i<=n;i++){//i要大于等于1而且要满足极大值坐标大于等于极小值,所以有max写法
        if(i-1>m)break;//挪过去左边i-1个数
        int pos=n-m+2*i-2;//确定右边再挪回到左边后最右边数坐标
        if(pos>n)pos=n;
        int r=a[pos];
        ans=min(ans,r-a[i]);
    }
    for(int i=min(n,2*n-m-1);i>=0;i--){
        if(n-i>m)break;
        int pos=m-2*n+2*i+1;
        if(pos<1)pos=1;
        int l=a[pos];
        ans=min(ans,a[i]-l);
    }
    cout<<ans;
    return 0;
}

思路是分别枚举极小值和极大值(本质上和枚举区间思想差不多)
比如枚举极小值
那么就把这个位置左边的都挪到右边,消耗一定步数
之后再挪回来,虽然极小值左边会多数,但它们一定和极小值相等
但是极小值不能太靠右
因为有m的限制
所以也要尝试枚举极大值

看来问题在于还没有形成正确思维,即枚举的思想,对于求极差最小问题,可以枚举极小值不变,然后改变极大值求最值
即求双变量最值,固定一个变另一个的办法
所以,后面的思路似乎更容易想出来!!!




tomousw
1个月前

https://www.luogu.com.cn/problem/P5740
java读入最好只用scanner和bufferedreader其中一个,不要混用,否则可能会RE




tomousw
1个月前
注意cout<<string::npos结果不是-1,如果题目要求找不到输出-1的话最好特判
scanf("%s\n")会把下一行首连续的空格吞掉,这样接下来gets结果就不对了
所以最好是scanf("%s")后getchar(),之后再gets(),确保无误
strlen()返回的结果类型是unsigned long long 类型,所以
for(int i=0;i<strlen(str);i++)
循环条件i<strlen(str)可能会出错,
应该用str[i]作为判断结束的条件
当发现计算复杂度没问题却TLE的情况,可能是判断条件数据被爆了,可以用exit(0)找一下到底是哪段代码的问题
见:
https://www.luogu.com.cn/problem/P1308
坎坷的debug过程
char[]不是全局变量时,一定记得赋一个'\0'!!!



tomousw
1个月前

https://www.luogu.com.cn/record/97328863

AC代码

n = eval(input())
strr=input()
list1 = []
list2 = []
list3 = []
list4 = []
list5 = []
for i in range(n):
    x = int(strr[i])
    if i > 0:
        list1 += ['.']
        list2 += ['.']
        list3 += ['.']
        list4 += ['.']
        list5 += ['.']
    if x == 0:
        list1 += ['X', 'X', 'X']
        list2 += ['X', '.', 'X']
        list3 += ['X', '.', 'X']
        list4 += ['X', '.', 'X']
        list5 += ['X', 'X', 'X']
    if x == 1:
        list1 += ['.', '.', 'X']
        list2 += ['.', '.', 'X']
        list3 += ['.', '.', 'X']
        list4 += ['.', '.', 'X']
        list5 += ['.', '.', 'X']
    if x == 2:
        list1 += ['X', 'X', 'X']
        list2 += ['.', '.', 'X']
        list3 += ['X', 'X', 'X']
        list4 += ['X', '.', '.']
        list5 += ['X', 'X', 'X']
    if x == 3:
        list1 += ['X', 'X', 'X']
        list2 += ['.', '.', 'X']
        list3 += ['X', 'X', 'X']
        list4 += ['.', '.', 'X']
        list5 += ['X', 'X', 'X']
    if x == 4:
        list1 += ['X', '.', 'X']
        list2 += ['X', '.', 'X']
        list3 += ['X', 'X', 'X']
        list4 += ['.', '.', 'X']
        list5 += ['.', '.', 'X']
    if x == 5:
        list1 += ['X', 'X', 'X']
        list2 += ['X', '.', '.']
        list3 += ['X', 'X', 'X']
        list4 += ['.', '.', 'X']
        list5 += ['X', 'X', 'X']
    if x == 6:
        list1 += ['X', 'X', 'X']
        list2 += ['X', '.', '.']
        list3 += ['X', 'X', 'X']
        list4 += ['X', '.', 'X']
        list5 += ['X', 'X', 'X']
    if x == 7:
        list1 += ['X', 'X', 'X']
        list2 += ['.', '.', 'X']
        list3 += ['.', '.', 'X']
        list4 += ['.', '.', 'X']
        list5 += ['.', '.', 'X']
    if x == 8:
        list1 += ['X', 'X', 'X']
        list2 += ['X', '.', 'X']
        list3 += ['X', 'X', 'X']
        list4 += ['X', '.', 'X']
        list5 += ['X', 'X', 'X']
    if x == 9:
        list1 += ['X', 'X', 'X']
        list2 += ['X', '.', 'X']
        list3 += ['X', 'X', 'X']
        list4 += ['.', '.', 'X']
        list5 += ['X', 'X', 'X']
print("".join(list1))
print("".join(list2))
print("".join(list3))
print("".join(list4))
print("".join(list5))

全RE代码,但洛谷IDE和本地都没问题

n = eval(input())
strr=input()
listA=list(int(x) for x in strr)#区别只是在这一行先转换为列表
list1 = []
list2 = []
list3 = []
list4 = []
list5 = []
for i in range(n):
    x = listA[i]
    if i > 0:
        list1 += ['.']
        list2 += ['.']
        list3 += ['.']
        list4 += ['.']
        list5 += ['.']
    if x == 0:
        list1 += ['X', 'X', 'X']
        list2 += ['X', '.', 'X']
        list3 += ['X', '.', 'X']
        list4 += ['X', '.', 'X']
        list5 += ['X', 'X', 'X']
    if x == 1:
        list1 += ['.', '.', 'X']
        list2 += ['.', '.', 'X']
        list3 += ['.', '.', 'X']
        list4 += ['.', '.', 'X']
        list5 += ['.', '.', 'X']
    if x == 2:
        list1 += ['X', 'X', 'X']
        list2 += ['.', '.', 'X']
        list3 += ['X', 'X', 'X']
        list4 += ['X', '.', '.']
        list5 += ['X', 'X', 'X']
    if x == 3:
        list1 += ['X', 'X', 'X']
        list2 += ['.', '.', 'X']
        list3 += ['X', 'X', 'X']
        list4 += ['.', '.', 'X']
        list5 += ['X', 'X', 'X']
    if x == 4:
        list1 += ['X', '.', 'X']
        list2 += ['X', '.', 'X']
        list3 += ['X', 'X', 'X']
        list4 += ['.', '.', 'X']
        list5 += ['.', '.', 'X']
    if x == 5:
        list1 += ['X', 'X', 'X']
        list2 += ['X', '.', '.']
        list3 += ['X', 'X', 'X']
        list4 += ['.', '.', 'X']
        list5 += ['X', 'X', 'X']
    if x == 6:
        list1 += ['X', 'X', 'X']
        list2 += ['X', '.', '.']
        list3 += ['X', 'X', 'X']
        list4 += ['X', '.', 'X']
        list5 += ['X', 'X', 'X']
    if x == 7:
        list1 += ['X', 'X', 'X']
        list2 += ['.', '.', 'X']
        list3 += ['.', '.', 'X']
        list4 += ['.', '.', 'X']
        list5 += ['.', '.', 'X']
    if x == 8:
        list1 += ['X', 'X', 'X']
        list2 += ['X', '.', 'X']
        list3 += ['X', 'X', 'X']
        list4 += ['X', '.', 'X']
        list5 += ['X', 'X', 'X']
    if x == 9:
        list1 += ['X', 'X', 'X']
        list2 += ['X', '.', 'X']
        list3 += ['X', 'X', 'X']
        list4 += ['.', '.', 'X']
        list5 += ['X', 'X', 'X']
print("".join(list1))
print("".join(list2))
print("".join(list3))
print("".join(list4))
print("".join(list5))



tomousw
1个月前

https://www.luogu.com.cn/problem/P1980

需要把其他类型变量转换为字符串是很常见的需求,那么怎么用什么方法实现更合适呢

AC代码

public static void main(String[] args) throws IOException {
    String[] strs=br.readLine().split(" ");
    n=Integer.parseInt(strs[0]);
    cp=Integer.parseInt(strs[1]);
    char cpc=Integer.toString(cp).charAt(0);
    for(int i=1;i<=n;i++){
        String s=String.valueOf(i);/////////////////////
        for(char c:s.toCharArray()){
            if(c==cpc)cnt++;
        }
    }
    System.out.println(cnt);

}

TLE+MLE代码

public static void main(String[] args) throws IOException {
    String[] strs=br.readLine().split(" ");
    n=Integer.parseInt(strs[0]);
    cp=Integer.parseInt(strs[1]);
    char cpc=Integer.toString(cp).charAt(0);
    for(int i=1;i<=n;i++){
        String s=String.format("%d",i);///////////////////////
        for(char c:s.toCharArray()){
            if(c==cpc)cnt++;
        }
    }
    System.out.println(cnt);

}

这表明在数据规模大且String.valueOf能实现时尽量不用格式化字符串

补充

String s=Integer.toString(i);//其实这样也能实现,而且速度和String.valueOf差不多



tomousw
1个月前

简单题,只要实现一下带负数除法取余,让余数在一定范围就行
但我根本没想到这一点,回过头看题目已经提示的很清楚了
而我却在想负进制表示是否唯一,怎么从正进制直接转换负进制什么的,思路完全偏了
还是一开始就没搞清楚进制表示的本质,不明白到底是怎么把10进制转换到base进制的,平时只是机械用正数不变进制的模板,没有深入思考,其次也没认真读题

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
#define speed_up ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

int r_get(int a,int b){
    int r=a%b;
    while(r<0)r-=b;
    while(r>=-b)r+=b;
    return r;
}


int main(){
    int n,base;
    cin>>n>>base;
    printf("%d=",n);
    vector<int> ans;
    while(n){
        int r= r_get(n,base);
        ans.push_back(r);
        n=(n-r)/base;
    }
    reverse(ans.begin(),ans.end());
    for(int i=0;i<ans.size();i++){
        int x=ans[i];
        if(x>=10)printf("%c",'A'+x-10);
        else printf("%d",x);
    }
    printf("(base%d)",base);
    return 0;
}