A. 小沙的炉石
链接：https://ac.nowcoder.com/acm/contest/23477/A
来源：牛客网
题目描述
小沙热衷于玩决斗法，今天他和他的弟弟玩起了炉石，弟弟特别特别的菜，但是为了照顾弟弟的自尊心，所以小沙想要恰好将弟弟斩杀。
恰好斩杀：弟弟的血量恰好变成0。
小沙当前的手上有nn张法术进攻牌，每张牌都会消耗一点法力，造成一点基础伤害，有mm张法术回复牌，不需要消耗法力值，每次可以恢复一点法力。小沙一开始有一点法力，法力没有上限。
他们都属于法术。
小沙场上有一个随从。他可以使你施法法术后使你的法术伤害+1。
每张法术进攻牌的伤害都等于法术伤害+基础伤害组成。
法术伤害初始为0。
你无法对该随从使用进攻法术牌。
随从也无法攻击。
现在小沙想问你，小沙现在能否恰好将弟弟斩杀。
输入描述:
第一行输入两个数1≤n≤109，0≤m≤1091≤n≤109，0≤m≤109分别代表小沙手上的法术进攻牌和法术回复牌。
第二行输入一个1≤k≤1051≤k≤105代表小沙有kk次询问
随后kk行每行输入一个整数1≤x≤10181≤x≤1018代表弟弟的血量
输出描述:
对于小沙的每一次询问，返回一行字符串
如果可以将弟弟斩杀输出“YES”（不带引号）
否则输出“NO”（不带引号）
示例1
输入
复制
2 1
3
1
4
6
输出
复制
YES
YES
NO
挺巧妙的思维题，比赛的时候理解错题意了，浪费半小时写了错的二分...
首先可以发现，我们能够控制出牌的顺序从而能够调节造成的伤害。如果想要造成的伤害最大，那么需要先出掉m张回复牌再出掉min(n, m + 1)张进攻牌（攻击次数由n和m共同约束）；如果想要造成的伤害最小，那么需要进攻一次回复一次，再进攻再回复（注意回复的时候也会涨攻击，因此每次造成的攻击是公差为2的等差数列）...
不妨设\(a = min(n, m + 1)\)，由等差数列求和公式，可得进攻a次情况下的攻击范围：\([\frac{(1+(2\times a-1))\times a}{2},a+\frac{(m+m+a-1)\times a}{2}]\)。可以证明限定攻击次数为a后绝大部分情况下这一段区间的任何伤害值都可以达到。
上面是固定攻击次数为min(n, m + 1)的情况，实际上为了达到完美击杀，并不一定要用光手里的攻击卡。根据给定的x，结合上面的公式，可以确定出想要达成完美击杀进行的攻击次数的候选值。因为上述攻击范围区间左端点化简后为\(a^2\)，令\(a^2=x\)得\(a=\lfloor sqrt(x)\rfloor\)，此即需要的攻击次数。可以验证，如果攻击a+1次，那么最终伤害区间左端点一定大于x，必然不可能造成完美击杀。这时还需要验证区间右端点是否大于等于x，直接把上面求出来的候选值\(a=\lfloor sqrt(x)\rfloor\)带入右端点表达式\(a+\frac{(m+m+a-1)\times a}{2}\)，判断其是否大于等于x即可。
#include <iostream>
#include <map>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <set>
#define int long long
#define ll long long
#define pb push_back
#define pii pair<int,int>
using namespace std;
ll n, m, k, x;
signed main() {
cin >> n >> m;
cin >> k;
for(int i = 1; i <= k; i++) {
ll x;
cin >> x;
ll atknum = min(n, m + 1);
ll s = (ll) sqrt(x);
atknum = min(atknum, s);
if(atknum + (m + m + atknum - 1) * atknum / 2 >= x) puts("YES");
else puts("NO");
}
return 0;
}
B. 小沙的杀球
链接：https://ac.nowcoder.com/acm/contest/23477/C
来源：牛客网
题目描述
小沙特别喜欢杀球（又菜又爱杀），加上小沙是个体能怪，所以他经常杀不死还喜欢杀，小沙只能杀到后场的高远球，如果是前场的小球则没有办法杀球，今天小沙和他的双打搭档一起训练杀球，我们假设小沙的体能一开始为X，并且每次杀球体能都会消耗a点，每次非杀球都会恢复b点。现给出一段01序列，代表搭档打过来的球是小球还是高远球（0代表小球，1代表高远球），请问小沙这一场能最多杀多少个球。小沙的体能不能为负数。
输入描述:
第一行3个整数 0≤x,a,b≤1090≤x,a,b≤109每个整数用空格间隔
第二行一行01字符串（字符串长度不超过106106） 代表搭档打过来的是小球还是高远球。
输出描述:
输出小沙的最多杀球次数
示例1
输入
复制
10 2 1
111111
输出
复制
5
说明
我们可以选择第2 3 4 5 6次杀球最多5次
纯签到，注意高远球不杀也没关系。
#include <iostream>
#include <map>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <set>
#define ll long long
#define pb push_back
#define pii pair<int,int>
using namespace std;
ll x, a, b;
int main() {
cin >> x >> a >> b;
string s;
cin >> s;
int ans = 0;
for(auto c : s) {
if(c == '0') x += b;
else {
if(x >= a) x -= a, ans++;
else x += b;
}
}
cout << ans;
return 0;
}
E. 小沙的长路
链接：https://ac.nowcoder.com/acm/contest/23477/E
来源：牛客网
题目描述
小沙有一个n个点的完全图(不知道定义可以点)，你可以给每条边选择方向，规定每条边只能走一次，请问n个点的完全图的最长路径，现在现在小沙想要知道它的最小值和最大值分别是多少？
输入描述:
输入一个正整数n≤109n≤109
输出描述:
一行内输出n个点的完全图，他的最长路的最小值和最大值，两个数中间用空格间隔
示例1
输入
复制
3
输出
复制
2 3
最大值比较好办，如果有奇数个点 ，那么每个点的度为偶，显然可以找一条欧拉回路（包含了n(n-1)/2条边）；如果有偶数个点，欧拉路需要两个奇度定点和若干个偶度顶点，那么实际上可以选择性去除n / 2 - 1条边使得原有两个奇度顶点和n - 2个偶度顶点， 可以找到一条欧拉路满足最长的要求（不太会严谨证明）。
最小值的话可以这样考虑，因为是先构造再遍历，不妨一开始从起点p0往任意方向走，设走到的点为p1，此时p0到p1的边方向已经确定，然后把剩下的与p1关联的边都指向p1（尽可能把路堵死）；这样就只能往后拓展，把与p0相关联的边都指向p0，再从与这些边关联的点里找一个点p2，再把与p2关联的剩余边指向p2...这样可以发现最小值就是n - 1。
#include <iostream>
#include <map>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <set>
#define ll long long
#define int long long
#define pb push_back
#define pii pair<int,int>
using namespace std;
signed main() {
ll n;
cin >> n;
ll mn, mx;
mn = n - 1;
if(n & 1) {
mx = (n - 1) * n / 2;
} else {
mx = (n - 1) * n / 2 - (n / 2 - 1);
}
cout << mn << " " << mx;
return 0;
}
F. 小沙的算数
链接：https://ac.nowcoder.com/acm/contest/23477/F
来源：牛客网
题目描述
小沙不会计数，所以他想从小学数学开始学起，今天老师布置了一大堆算数题，但爱耍小聪明的小沙发现这么多的算数题中，他们中间的符号都是++或者×× 并且每个题++和××的位置都是一样的
小沙想要快点去玩耍，所以求助好哥哥你帮帮他快速的计算出答案。
由于答案数字过大 所以我们对10000000071000000007取模
输入描述:
第一行 给定二个个数n代表有n个数进行计算 q代表有q次询问
(2≤n≤1062≤n≤106,1≤q≤1051≤q≤105)
第二行 给定一个一个长度为n-1的*+字符串 表示我们要进行的计算符号是什么
第三行 给定n个整数，代表这每个位置上的数字
随后q行每行两个数字x,y
代表着将第x个数字改成y
且x≤nx≤n
本题所有数均为正整数，且小于10000000071000000007
但并不保证计算过程中是否会出现大于10000000071000000007的值
输出描述:
对于每次查询，回答出整个算式的答案 每个答案占一行
（本题中的每次查询均不独立，也就是说每次查询修改之后的数，都会永远的修改）
示例1
输入
复制
5 3
++*+
1 1 3 1 1
4 2
1 7
5 6
输出
复制
9
15
20
多次修改操作想到用数据结构来维护。分析题目不难发现，可以把连续的加法段和连续的乘法段分开维护其运算结果，同时用map来维护每个位置对应到哪个加法段和哪个乘法段，修改的时候只需要修改对应的那个加法段/乘法段即可。需要注意乘法段维护时除法要用逆元来实现。细节挺多，详见代码。
#include <iostream>
#include <map>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <set>
#include <vector>
#define mod 1000000007
#define ll long long
#define int long long
#define pb push_back
#define pii pair<int,int>
using namespace std;
int n, q;
string s;
int a[1000005];
int totans = 0;
ll fpow(ll a, ll b) {
ll ans = 1;
ll res = a % mod;
while(b > 0) {
if(b & 1) ans = ans * res % mod;
b >>= 1;
res = res * res % mod;
}
return ans;
}
signed main() {
cin.tie(0);
ios::sync_with_stdio(false);
cin >> n >> q;
cin >> s;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
int cnt = 0, lst = 0;
vector<pair<int, int> > v2;
vector<int> v;
map<int, pair<int, bool> > mp;
s = s + '+';
for(int i = 0; i < s.size(); i++) {
if(s[i] == '*') {
if(!cnt) {
cnt = 1;
lst = i;
} else cnt++;
} else {
if(i > 0) {
if(s[i - 1] == '*') {
v2.pb(make_pair(lst, i - 1));
lst = i + 1;
cnt = 0;
}
}
}
}
lst = 1;
for(int i = 0; i < v2.size(); i++) {
v2[i].first += 1;
v2[i].second += 2;
ll ans = 1;
int now = v.size();
for(int j = v2[i].first; j <= v2[i].second; j++) {
ans = ans * a[j] % mod;
mp[j] = make_pair(now, 1);//1代表乘
}
v.pb(ans);
totans = (totans + ans) % mod;
if(v2[i].first - 1 >= lst && (i == 0 || v2[i - 1].second + 1 != v2[i].first)) {
ll ans = 0;
int now = v.size();
for(int j = lst; j <= v2[i].first - 1; j++) {
ans = (ans + a[j]) % mod;
mp[j] = make_pair(now, 0);//0代表加
}
v.pb(ans);
totans = (totans + ans) % mod;
}
lst = v2[i].second + 1;//不能放在上面的if里 要不然可能不会被更新
}
if(lst <= n) {
ll ans = 0;
int now = v.size();
for(int j = lst; j <= n; j++) {
ans = (ans + a[j]) % mod;
mp[j] = make_pair(now, 0);//0代表加
}
v.pb(ans);
totans = (totans + ans) % mod;
}
for(int i = 1; i <= q; i++) {
int x, y;
cin >> x >> y;
totans = (totans - v[mp[x].first] + mod) % mod;
if(mp[x].second == 0) {
v[mp[x].first] = (v[mp[x].first] - a[x] + mod) % mod;
v[mp[x].first] = (v[mp[x].first] + y) % mod;
a[x] = y;
} else {
v[mp[x].first] = v[mp[x].first] * fpow(a[x], mod - 2) % mod;
v[mp[x].first] = v[mp[x].first] * y % mod;
a[x] = y;
}
totans = (v[mp[x].first] + totans) % mod;
cout << totans << endl;
}
}
H. 小沙的数数
链接：https://ac.nowcoder.com/acm/contest/23477/H
来源：牛客网
题目描述
有一个a数组，我们已知他的长度为n，a[+]的和为m，请问如果我们想要a[⊕]的值最大，数组a在满足a[+]=m时有多少种情况
我们定义a[+]指a1+a2....ana1+a2....an的值
所以a[⊕]指a1a1⊕a2a2⊕a3a3....an....an的值 其中a数组全部都为非负整数。
答案对1e9+7取模 异或定义(不懂就点这个)
输入描述:
输入两个整数1≤n≤1018,0≤m≤10181≤n≤1018,0≤m≤1018
输出描述:
输出一个整数表示方案数
示例1
输入
复制
3 1
输出
复制
3
不妨从高位到低位逐位考虑。因为要求a[+]=m，那么每个a最高位的1肯定不能超过m的最高位的1，且要求异或和最大，那么对于所有a，一定有且只有一个a存在一个1位于m最高位1的这个位置，其他a这个位置为0。同样，m次高位为1也是相同的处理方法，为0的话则所有a的这一位都必须为0（否则和一定超过m）。这样不断处理下去，就可以知道答案实际上为\(n^{count(m)}\)，其中count(m)表示m的二进制表示中1的个数，即对于每个为1的二进制位，n个a中只有一个a的这一位是1；对于每个为0的二进制位，所有a的这一位为0，乘法原理计算即可。
#include <iostream>
#include <map>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <set>
#define mod (1000000000+7)
#define int long long
#define ll long long
#define pb push_back
#define pii pair<int,int>
using namespace std;
ll n, m, mm;
ll fpow(ll a, ll b) {
ll ans = 1;
ll res = a % mod;
while(b > 0) {
if(b & 1) ans = ans * res % mod;
b >>= 1;
res = res * res % mod;
}
return ans;
}
ll countBits(ll n) {
ll count = 0;
while(n != 0) {
n = n & (n-1);
count++;
}
return count;
}
signed main() {
cin >> n >> m;
mm = m;
ll cnt = countBits(mm);
if(cnt == 1) {
cout << n % mod;
} else {
cout << fpow(n, cnt) % mod;
}
return 0;
}
I. 小沙的构造
链接：https://ac.nowcoder.com/acm/contest/23477/I
来源：牛客网
题目描述
小沙的构造题没了，他很伤心，所以他想把这个构造送给你们，而你需要的就是彪起你的手速，抓紧抢到这题的一血。
这题小沙想让你构造出一串字符串，这个字符串有以下几个特点。
1，他是对称串，他关于这个字符串的垂直对称。例如"()",我们将他翻转过来他也是“()”，例如“p“翻转过来就是“q“。
2, 这个串串的所有字符都是除小写字母以外的可见字符（不包括空格）。
现在小沙想让你构造一个长度为nn的不同字符数量为mm的一个字符串。
可见字符如下:
!"#$%&'()*+,-./0123456789:;<=>?@[]^_`QWERTYUIOPASDFGHJKLZXCVBNM{}|~
其中具有对称性质的有
"!'*+-.08:=^_WTYUIOAHXVM|<>/[]{}()
输入描述:
第一行输入两个整数1≤n≤104,1≤m≤361≤n≤104,1≤m≤36。
输出描述:
如果可以构造出这样的一个字符串，便输出这个字符串
否则输出-1
示例1
输入
复制
3 1
输出
复制
OOO
示例2
输入
复制
3 3
输出
复制
<=>
比较恶心的字符串构造。首先将给出的字符分为两类，一类是自对称的一类是两个合起来对称的。构造的时候先使用合起来对称的再使用自对称的（否则很难调整）。细节太多，见代码吧oo
注意特判-1的情况（m=36比较坑，直接输出-1即可，其余情况详见代码）。
#include <iostream>
#include <map>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <set>
#define ll long long
#define pb push_back
#define pii pair<int,int>
using namespace std;
char c1[66] = {"\"!'*+-.08:=^_WTYUIOAHXVM|"};
char c2[66][3] = {{"<>"}, {"\\/"}, {"[]"}, {"{}"}, {"()"}};
int b[255] = { 0 };
int main() {
int n, m;
cin >> n >> m;
int len1 = 25, len2 = 5;
string ans1 = "", ans2 = "";
if(n < m || m == 36) {
puts("-1");
return 0;
}
int pos = 0, pos2 = 0;
for(int i = 0; i < n / 2; i++) {
if(m) {
if(pos2 < 5 && m > 2) {//一定是m > 2，否则过不了11 10这类样例
ans1 += c2[pos2][0];
ans2 = c2[pos2][1] + ans2;
pos2++;
m -= 2;
} else {
ans1 += c1[pos];
ans2 = c1[pos] + ans2;
pos++;
m--;
}
} else {
ans1 = ans1 + c1[0];
ans2 = c1[0] + ans2;
}
}
string ans = "";
if(n & 1) {
if(m) {
if(pos != 25) {
ans1 += c1[pos];
m--;
}
} else {
ans1 += c1[0];
}
}
ans = ans1 + ans2;
if(m) {
puts("-1");
} else {
cout << ans;
}
return 0;
}
//11 10
//5 5
//12 10
//13 12
//14 13
//35 2
K.小沙的步伐
纯签到，略过