题目描述
给定两个正整数A，B，请你计算 A / B的商和余数。
输入格式
共两行，第一行包含整数A，第二行包含整数B。
输出格式
共两行，第一行输出所求的商，第二行输出所求余数。
数据范围
1≤A的长度≤100000,
1≤B≤10000
样例
输入样例：
7
2
输出样例：
3
1
算法1
(暴力枚举) O(n2)O(n2)
blablabla
时间复杂度分析：blablabla
C++ 代码
#include #include #include using namespace std; //int r=0; vector div(vector &A,int B,int &r){//r传入r的地址，便于直接对余数r进行修改 vector C; for(int i=0;i<A.size();i++){//对A从最高位开始处理 r=r10+A[i];//将上次的余数10在加上当前位的数字，便是该位需要除的被除数 C.push_back(r/B);//所得即为商在这一位的数字 r=r%B; } //由于在除法运算中，高位到低位运算，因此C的前导零都在vector的前面而不是尾部，vector只有删除最后一个数字pop_back是常数复杂度，而对于删除第一位没有相应的库函数可以使用，而且删除第一位，其余位也要前移， //因此我们将C翻转，这样0就位于数组尾部，可以使用pop函数删除前导0 reverse(C.begin(),C.end()); while(C.size()>1&&C.back()==0) C.pop_back(); return C; } int main(){ string a; int B,r=0; //代表余数 cin>>a>>B; vector A; for(int i=0;i<a.size();i++) A.push_back(a[i]-‘0’);//注意这次的A是由高为传输至低位，由于在除法的手算过程中，发现从高位进行处理 //for(int i=0;i<A.size();i++) cout<<A[i]; //cout<<B; auto C = div(A,B,r); for(int i=C.size()-1;i>=0;i–) cout<<C[i];//将C从最高位传给最低位 cout<<endl<<r;//输出余数 cout<<endl; return 0; } // // Created by Genes on 2020/11/29. // // 高精度除法 #include #include #include #define ios ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr) using namespace std; vector div(vector &A, int b, int &r) { vector C; r = 0; //余数 for (int i = A.size() - 1; i >= 0; i–) { // 除法是从最高位开始算的 r = r * 10 + A[i];// 余数*10+当前这一位 C.push_back(r / b); r %= b; } reverse(C.begin(), C.end()); //倒过来是为了适配 加减乘–> 很多题目都不只一种运算 while (C.size() > 1 && C.back() == 0) { C.pop_back(); } return C; } int main() { ios; string a; int b; cin >> a >> b;
vector<int> A;// for (int i = a.size() - 1; i >= 0; i--) { A.push_back(a[i] - '0'); } int r; auto C = div(A, b, r); for (int i = C.size() - 1; i >= 0; i--) { cout << C[i]; } cout << endl << r << endl; return 0;
}
mex()：mex()：设集合S是一个非负整数集合，定义mex(S)mex(S)为求出不属于S的最小非负整数的运算，即：mes(S)=min[x],其中xmes(S)=min[x],其中x属于自然数，且xx不属于SS（用人话说就是不存在SS集合中的数中，最小的那个数）
SG()：SG()：在有向图中，对于每个节点xx，设从xx出发共有kk条有向边，分别达到节点y1，y2……yky1，y2……yk，定义SG(x)SG(x)为xx的后继节点的SGSG值构成的集合执行mex()mex()运算后的值
即：SG(x)=mex(SG(y1),SG(y2)…SG(yk))SG(x)=mex(SG(y1),SG(y2)…SG(yk))；（用人话说就是比后继节点的SGSG都小的值）
特别的整个图GG的SGSG值被定义为起点ss的SGSG值，即SG(G)=SG(s)SG(G)=SG(s)
上图标红的值就是每一个节点的SGSG值
性质：1.SG(i)=k，则i最大能到达的点的SG值为k−1。1.SG(i)=k，则i最大能到达的点的SG值为k−1。
2.非0可以走向0 2.非0可以走向0
3.0只能走向非0 3.0只能走向非0
定理：
对于一个图GG，如果SG(G)!=0SG(G)!=0，则先手必胜，反之必败
证明：
若SG(G)=!0SG(G)=!0，
1.根据性质2，先手必可以走向0，
2.因此留给后手的是0，根据性质3，后手只能走向非0
3.以此类推，后手始终无法走向0，后手永远处于非0，当先手到达终点的0时，先手获胜
（由此我们可以知道，有些事是命中注定的~~~）
反之同理，必败
定理：
对于n个图，如果SG(G1)SG(G1) ^ SG(G2)SG(G2) ^ … SG(Gn)!=0SG(Gn)!=0 ,则先手必胜，反之必败
证明（类似与Nim游戏）：
①当SG(Gi)=0SG(Gi)=0 时 ， xor=0xor=0 ， 显然先手必败
（PS：结束状态必是状态①，但状态①不一定是结束状态）
②当xor=x!=0xor=x!=0 时，因为肯定存在一个SG(xi)SG(xi)^x <SG(xi)<SG(xi),而根据SG()SG()的性质1可知，SG(k)SG(k)可以走到0−k−10−k−1的任何一个状态，
因此，必定可以从SG(xi)−>SG(xi)SG(xi)−>SG(xi)^xx ， 于是使得xor=0xor=0
③当xor=0xor=0时，当移动任何一个节点时，对应的SGSG值必然减小，可以证明：xor!=0xor!=0
下证：xor!=0xor!=0
假设:xor=0xor=0,则说明移动的那个节点的值并没有变化，即从SG(k)SG(k)变成了kk，但是这与SGSG函数的性质1相矛盾，因此不成立
证得：若先手面对的状态是xor!=0xor!=0,则先手方总能使xor=0xor=0，即使后手面对的永远是必败态直到结束状态①，因此先手必胜！
反之，必败！
C++ 代码
#include #include <unordered_set> #include using namespace std; const int N = 110 , M = 10010; int n , m; int s[N] , f[M]; int sg(int x) { if(f[x] != -1) return f[x];//记忆化搜索，如果f[x]已经被计算过，则直接返回
// 因为这题中较大堆的拆分情况独立于较小堆，因此有别于894.拆分-Nim，这里的S必须开成局部变量 unordered_set<int> S;//用一个哈希表来存每一个局面能到的所有情况，便于求mex for(int i = 0 ; i < m ; i++) if(x >= s[i]) S.insert(sg(x - s[i]));//如果可以减去s[i]，则添加到S中 for(int i = 0 ; ; i++)//求mex()，即找到最小并不在原集合中的数 if(!S.count(i)) return f[x] = i;
} int main() { cin >> m; for(int i = 0 ; i < m ; i++) cin >> s[i];
memset(f , -1 , sizeof f); cin >> n; int res = 0; while(n--) { int x; cin >> x; res ^= sg(x); } if(res) puts("Yes"); else puts("No"); return 0;
}
