前言：
还差B,J补完再写。
比赛感受：
还是很喜欢这套题的，可惜比赛时停电做了4题就溜了hhh
因为太菜了这篇只是写的简单题
第一次打rating赛，紫名快乐hhh
A： AOE还是单体？ （贪心）
思路：
对于血量大于x的用AOE，反之用单体。
所以可以按照血量从小到大排序，用AOE击败n-x个人，剩x个人用单体击败。
这也就是兰子姐姐题解里的临界值hh
代码：
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn=1e6+7;
ll a[maxn],n,x;
int main(){
cin>>n>>x;
ll sum=0;
for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];
if(x>=n){
cout<<sum<<endl;
return 0;
}
sort(a+1,a+1+n);
ll res=a[n-x]*x;
for(int i=n-x+1;i<=n;i++) res+=a[i]-a[n-x];
cout<<res<<endl;
return 0;
} C.白魔法师 （并查集判连通块）
题意：
树上有黑白两种点，问把一个黑点变成白色后树上白色连通块的最大值。
思路：
因为n的范围比较友好，所以可以统计出白色连通块的大小，然后枚举修改哪一个黑节点，当前的答案就是他的相邻节点的所有白色连通块大小加上本身。
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+7;
int root[maxn];///并查集 存储父节点
int cnt[maxn];///存储每个连通块的大小
char s[maxn];///存储每个点的颜色
vector<int>e[maxn];///存边
int n;
int Find(int x){
if(x!=root[x]) root[x]=Find(root[x]);
return root[x];
}
void Union(int x,int y){
x=Find(x),y=Find(y);
if(x!=y){
root[x]=y;
cnt[y]+=cnt[x];
}
}
int main()
{
cin>>n;
cin>>s+1;
for(int i=1;i<=n;i++)
root[i]=i,cnt[i]=1;
for(int i=1;i<n;i++){
int x,y;
cin>>x>>y;
e[x].push_back(y);
e[y].push_back(x);
if(s[x]=='W'&&s[y]=='W') Union(x,y);
}
int res=0;
for(int i=1;i<=n;i++)
if(s[i]=='W') res=max(res,cnt[Find(i)]);
else{
int tmp=1;
for(auto tt:e[i])
if(s[tt]=='W') tmp+=cnt[Find(tt)];
res=max(res,tmp);
}
cout<<res<<endl;
return 0;
} D.抽卡 （逆元）
思路：
1-抽不中卡的概率p。p为(a[i]-b[i])/a[i]的乘积。然后就可以用逆元求解了。
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn=1e6+7;
const ll mod=1e9+7;
ll a[maxn],b[maxn];
ll ksm(ll a,ll b){
ll p=mod;
ll res=1;
while(b){
//&运算当相应位上的数都是1时，该位取1，否则该为0。
if(b&1)
res=1ll*res*a%p;//转换为ll型
a=1ll*a*a%p;
b>>=1;//十进制下每除10整数位就退一位
}
return res;
}
int main(){
ll n;cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
ll res=1;
for(int i=1;i<=n;i++){
res=res*(a[i]-b[i])%mod*ksm(a[i],mod-2)%mod;
}
res=(1-res+mod)%mod;
cout<<res<<endl;
return 0;
} E.点击消除（栈）
思路：
用栈模拟一下消除的过程即可，如果栈为空或栈顶元素与当前元素不相等，当前元素就可以被放入栈中；否则，当前元素和栈顶元素消除，弹出栈顶元素。
代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;cin>>s;
string res="";
stack<char>st;
for(int i=0;i<s.size();i++){
if(st.empty()||st.top()!=s[i]) st.push(s[i]);
else if(st.top()==s[i]) st.pop();
}
bool flag=0;
if(st.empty()) flag=1;
while(!st.empty()){
res=res+st.top();
st.pop();
}
if(flag) puts("0");
else{
for(int i=res.size()-1;i>=0;i--) cout<<res[i];
}
return 0;
} E.疯狂的自我检索者(签到题)
思路：
要想平均分最小肯定是总和最小，这时候隐藏的分数都为1；
想要平均分最大肯定是总和最大，这时候隐藏的分数都为0；
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+7;
int a[maxn],n,m;
int main(){
cin>>n>>m;
int sum=0;
for(int i=1;i<=n-m;i++)
cin>>a[i],sum+=a[i];
double maxx=1.0*(sum+5*m)/n,minn=1.0*(sum+m)/n;
printf("%.5f %.5f\n",minn,maxx);
return 0;
} G.解方程（二分）
思路：
盲猜具有单调性（手动滑稽）。
其实是一个单调递增的函数。
二分答案即可，但是需要把eps设的小一点。
代码：
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const double eps=1e-7;
ll a,b,c;
bool check(double mid)
{
if((pow(mid,a)+log(mid)*b)>=c) return 1;
return 0;
}
int main()
{
cin>>a>>b>>c;
double l=0,r=1e9;
while(r>=l){
double mid=1.0*(l+r)/2;
if(check(mid)) r=mid-eps;
else l=mid+eps;
}
printf("%.14f\n",r);
return 0;
} H. 神奇的字母（二） （map+EOF）
思路：
用map记录一下出现的次数即可。考点是如何输入，真的是小白必须要知道的知识点啊。
代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
map<char,int>mp;
string s;
while(getline(cin,s)){
for(int i=0;i<s.size();i++)
if(s[i]!=' ') mp[s[i]]++;
}
int maxx=0;
char pos;
for(auto it=mp.begin();it!=mp.end();it++)
if(maxx<it->second) maxx=it->second,pos=it->first;
cout<<pos<<endl;
return 0;
} I. 十字爆破 （开数组的小技巧）
思路：
用x[i]表示第i行的得分之和，y[i]表示第i列的得分之和。
那么每个格子(i,j)的得分就是x[i]+y[j]-a[i] [j]
但是数据范围是n*m=1e5，直接开二维数组又会爆内存。
可以用下面两种解决方法：一是用vector，二是开成a[n+10] [m+10]类型的。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
#define I_int ll
#define inf 0x3f3f3f3f
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
char F[200];
inline void out(I_int x) {
if (x == 0) return (void) (putchar('0'));
I_int tmp = x > 0 ? x : -x;
if (x < 0) putchar('-');
int cnt = 0;
while (tmp > 0) {
F[cnt++] = tmp % 10 + '0';
tmp /= 10;
}
while (cnt > 0) putchar(F[--cnt]);
//cout<<" ";
}
const int maxn=1e6+7;
ll x[maxn],y[maxn];
void AC(){
int n,m;
n=read();m=read();
ll a[n+5][m+5];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
ll t=read();
a[i][j]=t;
x[i]+=t;y[j]+=t;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
out(x[i]+y[j]-a[i][j]);
if(j==m) puts("");
else cout<<" ";
}
}
int main(){
AC();
return 0;
}
京公网安备 11010502036488号