观察到以下规律：如果[1, 2, ... , n]的第k<n位和最后一位交换，那么[0,n)依旧是一个排列，而[0,k]不是一个排列。所以算法如下：从1 2 3 4 5 ... n开始对每个'0'的位置 i，总是找其后面的第一个'1'位置 j，交换perm[i],perm[j]。 #include <bits/stdc++.h> using namespace std; int main() { int n; string s; cin >> n >> s; vector<int> perm(n); int j=0; int i; for ...

思路：从全集S中随机选取p个元素后，形成了两个集合。S1：选取的已知的p个元素S2：剩下未知的元素如何根据S1和S2做出必胜的判断——即一定不会抽到两个相同元素？1、要求S1的元素包含至少两种不同的类或者某个类的全部元素。根据鸽巢原理可得p1=max(占比最大的类的元素的个数）2、要求S2包含每个类的元素恰为一个，共有k个元素。这里要求p2=|S|-k选取以上的两个数的最小值：min(p1,p2)即可。 #include <iostream> using namespace std; int check() { int n; cin >> n; long tmp; lo...

思路在于：考虑此前已经操作了n次，而目前还有a个空瓶，计划借c个空瓶。可以列出以下表格，当(a+c)/3==c时，正好可以还c个空瓶，化简得a=2c。实际上2c<=a<2(c+1)时，都可以偿还c个空瓶。a=2c（剩0个空瓶）或者a=2c+1（剩1个空瓶） a c 2 1 4 2 6 3 每一步，持有a个空瓶，都可以考虑借c个瓶子（0<=c<=a/2）如果a大于等于3如果借c个空瓶，得到 (a+c)/3个饮料，喝完得 c+(a-2c)%3+(a-2c)/3 个空瓶。减去c得(a-2c)%3+(a-2c)/3。如果不借，总可以把a个空瓶置换成a/3饮料，喝完这些饮料后，得...

思路：把次件转换为主件。举个例子，输入如下 100 5 80 2 0 40 5 1 ==>对应选择该次件和其主件的情况，可以转换为 40+80 2+5 0 20 5 1 ==>对应选择该次件和其主件的情况，可以转换为 20+80 2+5 0 (140 9 0) ==>新添加的主件，对应两个次件都选的情况，可以转换为 20+40+80 2+2+5 0 40 3 0 50 2 0 可以看出，次件的组合加上对应主件就相当于一个新的主件。所以我们需要对输入进行处理，把次件转换成主件。而对于主件，就可以用01背包的方法去做了。这个方法应该可以处理任意n个次件的情况。这里给出可以通过但没...