hihocoder编程练习赛55
A
描述
给定:
1)N个正整数A1, A2, … AN;
2)P个加号+和Q个减号-; (P+Q=N-1)
3)K对括号()
请你使用全部整数、加减号和括号，组成一个合法的算式(A1~AN在算式中的顺序随意)，使得算式的结果最大。
注意加减号只能作为二元运算符出现在算式中，不能作为正负号。
括号可以出现在算式最左和最右，例如(((1+2)))是合法的。
例如对于样例数据，(2-1)+3或3+(2-1)等都是结果最大的算式。
输入
第一行包含4个整数，N，P, Q和K。
第二行包含N个整数A1, A2, … AN。
2 ≤ N ≤ 100 P+Q+1=N 0 ≤ K ≤ 10
1 ≤ Ai ≤ 1000
输出
最大算式结果
样例输入
3 1 1 1
1 2 3
样例输出
4
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| using namespace std; int n,p,q,k; int a[maxn]; bool cmp(int x,int y){ return x>y; } int main(){ // freopen("input.txt","r",stdin); cin>>n>>p>>q>>k; for(int i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+1+n,cmp); int ans=0; if(k==0){ for(int i=1;i<=n;i++){ if(i<=p+1) ans+=a[i]; else ans-=a[i]; } } else{ for(int i=1;i<n;i++) ans+=a[i]; ans-=a[n]; } cout<<ans<<endl; return 0; }
|
思路
贪心
排序 若没有括号 从大开始先补加号后补减号
若有括号 根据-(最小-最大-次大-···) 只需要一个括号就可以把除最小外 其余均变成正数 所以答案就是前n-1大减去最小值
B
描述
我们称两个长度相等的字符串A和B是朋友字符串，当且仅当
1)A和B只有两个位置i和j的对应字符不同，即A[i] ≠ B[i]且A[j] ≠ B[j]
2)一个字符串如果交换位于i和j的字符将变成另一个字符串。
例如conserve和converse就是朋友字符串。
现在给定N个长度相同的字符串S1, S2, … SN，请你求出其中有多少对朋友字符串。
输入
第一行包含一个整数N。
以下N行每行一个只包含小写字母的字符串Si。
对于70%的数据，1 ≤ N ≤ 1000,
对于100%的数据，1 ≤ N ≤ 20000, |Si| ≤ 10
输出
一个整数代表答案
样例输入
4
aaba
aaab
abaa
baaa
样例输出
6
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| using namespace std; int n; map<string,int>mp; char s[maxn]; int main(){ // freopen("input.txt","r",stdin); scanf("%d",&n); int ans=0; for(int i=1;i<=n;i++){ scanf("%s",s); int len=strlen(s); for(int i=0;i<len;i++){ for(int j=i+1;j<len;j++){ if(s[i]!=s[j]){ swap(s[i],s[j]); if(mp.count(s)) ans+=mp[s]; swap(s[i],s[j]); } } } mp[s]++; } cout<<ans<<endl; return 0; }
|
思路
注意len<=10 所以直接暴力 map存储每个字符串出现的次数
对于每个字符串暴力交换2个不同的位置 判断交换后的字符串是否出现 若出现 加上出现的次数
C
描述
给定N个闭区间[A1, B1], [A2, B2], [A3, B3] … [AN, BN]，请你计算没有被这些区间覆盖的第K小的正整数是多少？
输入
第一行包含两个整数N和Q，分别代表区间数目和询问数目。
以下N行每行包含两个整数Ai和Bi。
最后一行包含Q个整数，K1, K2, … KQ，代表Q次询问。
对于50%的数据，1 ≤ N, Q ≤ 1000
对于100%的数据，1 ≤ N, Q ≤ 100000 0 ≤ Ai ≤ Bi ≤ 1000000000 1 ≤ Ki ≤ 1000000000
输出
对于每次询问Ki，输出没有被这些区间覆盖的第Ki小的正整数是多少。
每个答案一行。
样例输入
3 3
10 20
15 22
30 40
5
10
15
样例输出
5
23
28
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
| using namespace std; int n,q; vector<pair<int,int> >v1,v2; int pre_len[maxn]; int main(){ // freopen("input.txt","r",stdin); cin>>n>>q; for(int i=1;i<=n;i++){ int x,y; cin>>x>>y; v1.push_back(mp(x,y)); } sort(v1.begin(),v1.end()); if(v1[0].first>1) v2.push_back(mp(1,v1[0].first-1)); int ed=v1[0].second; for(int i=1;i<v1.size();i++){ if(v1[i].first>ed+1){ v2.push_back(mp(ed+1,v1[i].first-1)); ed=v1[i].second; } else ed=max(ed,v1[i].second); } v2.push_back(mp(ed+1,2000000000)); pre_len[0]=v2[0].second-v2[0].first+1; for(int i=1;i<v2.size();i++){ pre_len[i]+=pre_len[i-1]+v2[i].second-v2[i].first+1; } // for(int i=0;i<v2.size();i++) cout<<pre_len[i]<<endl; while(q--){ int k; cin>>k; int l=0,r=v2.size(); int ans=0; while(l<=r){ int mid=l+r>>1; if(pre_len[mid]>=k) r=mid-1,ans=mid; else l=mid+1; } if(ans>0) k-=pre_len[ans-1]; cout<<v2[ans].first+k-1<<endl; } return 0; }
|
思路
所有区间按照左端点排序 v2记录所有未被覆盖的区间 用pre_len求出这些区间元素个数的前缀和
二分k所在的区间位置 找到大于等于k的第一个位置
两个wa点：
1.二分找到的ans要减去pre_len[ans-1]才是在第ans个区间所在的位置 但如果ans为0 无需减
2.v2 push的区间右限 由于ai小于1e9 k小于1e9 所以区间的右限最多为2e9
