Posts

本题 由 Red 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。 严禁抄袭，侵权必究。代码仅当参考使用。 挂彩灯 描述 有一堆彩灯，红色绿色两种颜色，现在要把它们串在一起，要求每个红灯后面至少要有1个绿灯，求一共有多少种不同的串法 输入 第1行是一个正整数n，表示测试案例的数量 第2到第n+1行是n组测试数据，每行数据有两个正整数，分别表示红灯的数量和绿灯的数量 输出 针对每行测试数据，输出不同的串法数量。（答案不会超过50万） 每组案例输出完都要换行。 样例输入 1 2 3 样例输出 3 提示说明 2个红灯3个绿灯合法的串法有：绿红绿红绿、红绿绿红绿、红绿红绿绿，一共3种 思路 高中排列组合题，应该来说思路是很直观的。 首先彩灯要遵循“一红配一绿”的规则，那么剩下需要进行排列的彩灯也就是用绿彩灯减去红彩灯数剩下的进行插空。那么问题就变成了十分经典的一种排列组合模型——将绿球排成一排，然后再从中挑出若干个与红球进行配对。因为根据题意，红球绝对不可能排在队头，所有这里只需要将 C（绿球数，红球数）算出来就行。并且根据排列组合C（m,n）=m!/n!*(m-n)!的特性，当红灯数大于绿灯数一半后，可以将超出部分消去，因此只需要对g-r进行计算就行 需要注意的是，为了防止数据超出，这里数据类型需要使用long long 代码[C++] [Forlogin] #include <iostream> #include <cmath> #include<limits.h> using namespace std; int main() { int n; cin >> n; while (n--) { long long int r, g, c, mul1 = 1, mul2 = 1; cin >> r >> g; if (r > g) { cout << 0; } else if (r == g || r == 0) { cout << 1; } else { if (r > g / 2) { r = g - r; } for (int i = 1; i<=r; i++) { mul1 = mul1 * g; mul2 = mul2 * i; g--; } c = mul1 / mul2; cout << c; } cout << endl; } return 0; }[/Forlogin]

本题 由 Red 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。 严禁抄袭，侵权必究。代码仅当参考使用。 第2题 描述 世人皆好奇lxy的体重，但lxy自己不愿意说，她由两个舍友lwj和knt表示可以透露lxy的体重，但不会直接说出数值。目前已知lxy的体重是1到300斤之间的某个整数（包括1和300）。 lwj喜欢透露lxy的体重除以a的余数等于b，knt喜欢透露lxy的体重大于d或者小于d。当她们透露了一定的消息以后，就可以唯一确定lxy的体重，当然也有可能因为自相矛盾而导致无解，也有可能有多个可能的解。 现有lwj和knt的一系列透露的消息，分别是lwj一句话knt一句话这样的循环，想知道最终是否能够确定lxy的体重。 输入 只有一组测试案例。 第1行是一个正整数n，表示lwj和knt一共透露了多少句话（两个人说话的总和） 第2到第n+1行是她们说的n句话，其中第偶数行是lwj说的，每行包括两个整数a、b（a>b>=0），表示lxy的体重除以a的余数等于b。第奇数行是knt说的，每行包括两个整数c和d（c只会是1或者-1，d>=0），如果c=1，表示lxy的体重大于d；如果c=-1，则表示lxy的体重小于d。 输出 如果根据她们说的n句话，lxy的体重是无解的，则输出-1；如果lxy的体重有多个合法的解，则输出0；如果lxy的体重有唯一解，则输出体重值。不要换行。 样例输入 4 12 0 1 110 10 0 -1 130 样例输出 120 提示说明 4句话分别代表体重除以12余0，体重大于110，体重除以10余0，体重小于130，故可以断定lxy的体重是120 思路 一般的思路是很直观的，那就是将所有数读进一个数组后再在knt提供的最小和最大数之间进行遍历，挨个判断余数是否相符就行 但事情并没有这么简单，你会发现在还没学二维数组之前，你很难将lwj提供的数据储存起来再参与到余数判断的遍历中（当然也有办法） 所有一般的思路永远没有二般的好用，下面就来介绍一下 结合对余数的理解，可以用累加的方式，从b开始，每次加a加到<=300为止。又因为一共有(n+1)/2行的要求，所有符合这个要求的数就是满足条件，在计数器cnt中就能+1了 需要注意的是，在判断“体重无解”或“体重有解”后要及时跳出程序，否则会出现多次输出的情况。具体操作就是在满足条件的最后都加上break 代码[C++] [Forlogin] #include<iostream> #include<limits.h> using namespace std; int main() { int n,i=2,wight[301]={0},min=1,max=300,cnt=0,k[2]={0},md=0; cin>>n; while(i<=n+1){ if(i%2==0){ int a,b; cin>>a>>b; for (int j=b;j<=300;j+=a) wight[j]++; }else{ int c,d; cin>>c>>d; if(c==1&&d>min) min=d; if(c==-1&&d<max) max=d; if(max<=min) {cout<<"-1";md=1;break;} } i++; }if(md!=1){ for (int j=min;j<=max;j++){ if(wight[j]==(n+1)/2){ k[0]=j; cnt++; if(cnt>1){ cout<<"0"; break; } } } if(cnt==0) cout<<"-1"; if(cnt==1) cout<<k[0]; } return 0; }[/Forlogin] 题外话 这题卡了超久 ...

听我一句劝，不要擅自挂CDN！！！ 事情经过 前些天到百度闲逛，便突发奇想地想重新搭个屋子 [没有部落格的人绝不认输] 于是一番走街串巷后，来到了一家奇怪的商店，看到了一个奇怪的商品 超！139！这还不冲他！ …… 在买下这台香港服务器后，又是一番折腾，于是便搭好了这个小屋 虽然但是，这么冲明的在我就想，搭完Blog可不能白白浪费了这整整10M的带宽 于是我就对下面这个地方产生了人类原始的好奇心 好的，打不开，是时候拿起手里的小飞机尝试一下了 简单思路 既然有了一台在firewall以外服务器，同时经过尝试后可以与google.com直接ping通，那么接下来就需要一个合适的协议来搭建本地与主机之间的联系 众所周知，在TCP/IP四层结构里，firewall主要作用于传输层和网络层，通过对数据包的加密方式、请求内容、协议或端口等进行特殊筛选，从而达到无法出入境的效果 firewall的存在也只是让传统http的请求过程多了一步筛选（当然，现在的firewall也变得越来越聪明，会自动发起对服务器的请求来判断是否存在异常，本文暂不会提到应对手段） 于是就有dalao想出了一种奇妙的方法来规避这样定筛选，就是**欺骗** 欺骗的原理也很简单，只需要对发送到请求进行加密就行 事前准备 使用协议:Vmess 工具:V2ray、Putty 安排

本题 由 Red 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。 严禁抄袭，侵权必究。代码仅当参考使用。 第10题 描述 N个学生去海岛游玩，只带了一个hrr牌充电宝，可以为所有学生的手机充电。第i个学生的手机具有百分之p[i]的电量，充电宝总共可以充百分之M的电量。问最多可以有几台手机的电量达到百分之百。 输入 只有一组案例。 第一行是两个整数N和M(0≤N≤100,0≤M≤10000)，第二行包含N个整数p[i] (0≤p[i]≤100)表示第i台手机剩余电量的百分比。 输出 一个整数，表示最多可以充的手机台数。不要换行。 样例输入 3 10 100 99 90 样例输出 2 思路 很简单，只要将每台手机存到数组里然后再挨个减100，最后判断剩余电量M能够撑到第几台手机不小于0即可 代码[C语言] [Forlogin] #include<iostream> #include<algorithm> using namespace std; int main(){ int a[10000]={0},N,M,cnt=0; cin>>N; cin>>M; for(int i=0;i<N;i++){ cin>>a[i]; a[i]=100-a[i]; } sort(a,a+N); for(int i=0;i<N;i++){ M-=a[i]; if(M<0){ break; } cnt++; } printf("%d",cnt); }[/Forlogin]

本题 由 Red 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。 严禁抄袭，侵权必究。代码仅当参考使用。 第9题 描述 把一堆数字按照最小数—最大数—第二小数—第二大数—第三小数—第三大数…这样的规律输出所有的数字。 输入 只有一组案例。 一个正整数n，然后是n个整数。（n是偶数） 输出 把这n个整数按照最小数—最大数—第二小数—第二大数—第三小数—第三大数…这样的规律输出所有的数字。每个数字之间有一个空格，最后的数字后面没有空格和换行 样例输入 6 1 2 3 4 5 6 样例输出 1 6 2 5 3 4 思路 有两种想法，最直观的一种就是开个俩数组，数组a用来储存输入，另一个数组b用来储存将a遍历后的“一大一小”，说白点就是说得挨个比较一遍。时间复杂度为O（n^n）。这种算法对于样例数据这样小的数字还是可以接受的，缺点就在于没法承受太多组数字，每次比较完后还不能比之前的数字来得小（大），显然加大了工作量。 既然一般的方法不行，那就用二般的方法。我们可以把此次作业第1题抄过来，将数组a从小到大排完后，分别正序和倒序输出即可。这样便将时间复杂度控制在了O（n^2） 代码[C语言] [Forlogin] #include<stdio.h> #include<limits.h> int main(){ int n,min,a[10000]={0}; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d",&a[i]); } for(int i=0;i<n;i++){ for(int t=i+1;t<n;t++){ if(a[i]>a[t]){ min=a[i]; a[i]=a[t]; a[t]=min; } } } for(int i=0;i<=(n/2)-1;i++){ printf("%d ",a[i]); printf("%d",a[(n-1)-i]); if(i!=(n/2)-1){ printf(" "); } } }[/Forlogin] 代码[C++] [Forlogin] #include<iostream> #include<limits.h> using namespace std; int main(){ int n,min,a[10000]={0}; cin<<n; for(int i=0;i<n;i++){ cin<<a[i]; } for(int i=0;i<n;i++){ for(int t=i+1;t<n;t++){ if(a[i]>a[t]){ min=a[i]; a[i]=a[t]; a[t]=min; } } } for(int i=0;i<=(n/2)-1;i++){ cout>>a[i]; cout>>a[(n-1)-i]); if(i!=(n/2)-1){ cout>>" "; } } }[/Forlogin] 发布用于测试小屋页面显示功能 ...