广义鸽巢原理： 把（mn－1）个物体放入n个抽屉中，其中必有一个抽屉中至多有（m—1）个物体。
错误证明：
假设不存在抽屉中至多有（m-1）个物体
即所有抽屉，每个抽屉物体数都大于m-1
那么物体总数大于mn-n
被卡住
因为这样推不出矛盾
改成如下证明：
假设不存在抽屉中至多有（m—1）个物体
即所有抽屉，每个抽屉物体数都大于m-1，即大于等于m
那么物体总数大于等于mn
推出了矛盾
由此可见离散数学中由个体满足的性质拓展到整体时，x>=y和x>y-1不能当作等价的v条件
因为两边乘以倍数后容易放缩过度，而转换为含有大（小）于等于的式子放缩更精密，不容易放缩过度
上面问题是学习P180.排书的上下取整恒等式时发现的
参考链接，留待日后学习
先记住结论：
#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;
}
代码本身应该是有问题的，第一次调用应该是没有返回值的
但是不知道为什么返回了第二次调用返回的结果
// #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
代码：
#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;
}
}
}
这种比赛居然还出图论题
没复习图论的下场
我居然还调了半小时
可太没经验了
这个题显然可以调大数据范围，还可以考个二分什么的
莲子正在研究分子的运动。
每个分子都有一个速度，约定正方向为正，负方向为负。分子的数量极多，速度又并不一致，看上去杂乱无章。于是莲子希望调整部分分子的速度，使得最终分子们看上去整齐。
莲子给定了 $n$ 个整数 $a_1,a_2,\cdots a_n$，描述每个分子。现在她可以进行至多 $m$ 次操作（也可以一次也不进行），每次操作可以执行以下两条之一：
现在莲子希望需要最小化最终序列的极差（最大值减去最小值的差）。请求出最小的极差。
例如，对于序列 $a={5,1,4}$，可以进行如下几次操作：
这两次操作后得到的序列为 ${1,4,4}$。最大值减去最小值的差为 $|4-1|=3$。
当然，这种操作方式得到的极差并非最小。最优策略是，先将最大值 $a_1=5$ 变成目前的最小值 $1$，再把此时的最大值 $a_3=4$ 变成目前的最小值 $1$。此时序列为 ${1,1,1}$，得到的极差 $|1-1|=0$ 是所有策略中最小的。
3 2
5 1 4
0
8 0
1 2 3 4 5 6 7 8
7
8 3
1 5 5 5 6 6 9 10
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$。
#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的限制
所以也要尝试枚举极大值
看来问题在于还没有形成正确思维，即枚举的思想，对于求极差最小问题，可以枚举极小值不变，然后改变极大值求最值
即求双变量最值，固定一个变另一个的办法
所以，后面的思路似乎更容易想出来！！！
注意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'！！！
https://www.luogu.com.cn/record/97328863
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))
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))
https://www.luogu.com.cn/problem/P1980
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);
}
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 s=Integer.toString(i);//其实这样也能实现，而且速度和String.valueOf差不多
简单题，只要实现一下带负数除法取余，让余数在一定范围就行
但我根本没想到这一点，回过头看题目已经提示的很清楚了
而我却在想负进制表示是否唯一，怎么从正进制直接转换负进制什么的，思路完全偏了
还是一开始就没搞清楚进制表示的本质，不明白到底是怎么把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;
}
