这周成绩还算可以，但是仍有些遗憾。。。
本来D题肯定可以做出来的，但是由于水群过度+混迹B站Z站没怎么好好想。。。
T1：
水题，n^2枚举即可，（HuHao状压真的♂骚）
code:
#include<bits/stdc++.h>
using namespace std;
int n,a[110][110];
int ans,b[110];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++){
int flag=1;
for(int j=1;j<=n;j++)if(a[i][j]==1||a[i][j]==3) flag=0;
if(flag) b[++ans]=i;
}
printf("%d\n",ans);
for(int i=1;i<=ans;i++)printf("%d ",b[i]);
return 0;
}T2:
在吴教练眼中的“小学数学题+DP”什么不存在的吧。。。
式子什么的不会推，没有经验，多做做题吧。。（沉迷枚举，DP基本没做过、、）
我们设f[i][j][k]表示分别剩下i,j,k个人的概率
然后发现f[i-1][j][k]和f[i][j-1][k]和f[i][j][k-1]都可以继承这个值，但是要除以一个概率
最后统计一下答案即可
code:
#include<bits/stdc++.h>
using namespace std;
int a,b,c;
double f[110][110][110];
double ans1,ans2,ans3;
int main(){
scanf("%d%d%d",&a,&b,&c);
f[a][b][c]=1;
for(int i=a;i>=1;i--)
for(int j=b;j>=1;j--)
for(int k=c;k>=1;k--){
double cnt=i*j+j*k+i*k;
f[i-1][j][k]+=f[i][j][k]*(i*k/cnt);
f[i][j-1][k]+=f[i][j][k]*(i*j/cnt);
f[i][j][k-1]+=f[i][j][k]*(j*k/cnt);
}
for(int i=0;i<=a;i++)
for(int j=0;j<=b;j++)
ans1+=f[i][j][0];
for(int i=0;i<=a;i++)
for(int j=0;j<=c;j++)
ans2+=f[i][0][j];
for(int i=0;i<=b;i++)
for(int j=0;j<=c;j++)
ans3+=f[0][i][j];
printf("%.9lf %.9lf %.9lf",ans1,ans3,ans2);
return 0;
}T3:
这道题表示只会nlogn算法。。。太菜了啊。。。
模拟交换，然后用树状数组做一遍即可。。。
code:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,a,mx,b;
int bel[10000010];
int c[10000010];
ll ans;
void swap(int &x,int &y){int t=x;x=y;y=t;return;}
int read(){
int x=0;
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x;
}
int lowbit(int x){return x&-x;}
void change(int x){
// if(!x) x=1;
while(x<=mx){
c[x]++;
x+=lowbit(x);
}
return;
}
ll query(int x){
ll cnt=0;
while(x){
cnt+=c[x];
x-=lowbit(x);
}
return cnt;
}
int main(){
n=read();
mx=-1;
for(int i=1;i<=1e7;i++)bel[i]=i;
for(int i=1;i<=n;i++){
a=read();b=read();
swap(bel[a],bel[b]);
mx=max(mx,max(a,b));
}
for(int i=1;i<=mx;i++){
change(bel[i]);
ans+=i-query(bel[i]);
}
// for(int i=1;i<=mx;i++)printf("%d ",bel[i]);
// puts("");
printf("%lld",ans);
return 0;
}T4:
首先发现首尾两棵树肯定分别向左向右倒，然后再考虑每棵树：
得到一个贪心策略:如果可以往左放就往左放（之前已经计算过，显然比右边优），如果可以往右放再往右放（优先左）
code：
#include<bits/stdc++.h>
using namespace std;
int n,x[1000010],h[100010];
//struct node{
// int l,r,p;
//}a[200010];
int ans;
//bool cmp(node u,node v){return u.r<v.r;}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d",&x[i],&h[i]);
x[n+1]=1e10;
for(int i=2;i<=n;i++){
if(x[i]-x[i-1]>h[i]) ans++;
else if(x[i+1]-x[i]>h[i]){
x[i]+=h[i];
ans++;
}
}
printf("%d",++ans);
return 0;
}T5:
第一眼看到就知道是记忆化搜索+玄学猜结论。。。
但是我就是要写BFS+队列（傲娇）
最后判断一下终点的情况：
1.可以直接掉下去，那么如果终点周围有联通的点就可以了
2.不可以直接掉，要求终点周围有两个以上的联通的点
code:
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
int n,m,sx,sy;
int ex,ey,s,t;
char mp[510][510];
int dis[510][510];
pair<int,int> que[100010];
vector<pair<int,int> > edge[510][510];
int nxt[5][2]={0,0,-1,0,1,0,0,-1,0,1};
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%s",mp[i]+1);
scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
memset(dis,127,sizeof(dis));
dis[sx][sy]=0;
que[++t]=make_pair(sx,sy);
while(s<t){
int ux=que[++s].fi;
int uy=que[s].se;
for(int i=1;i<=4;i++){
int tx=ux+nxt[i][0];
int ty=uy+nxt[i][1];
if(mp[tx][ty]=='.'&&dis[tx][ty]){
dis[tx][ty]=0;
que[++t]=make_pair(tx,ty);
}
}
}
int cnt=0;
for(int i=1;i<=4;i++){
int tx=ex+nxt[i][0];
int ty=ey+nxt[i][1];
if(mp[tx][ty]=='.') cnt++;
}
if(!dis[ex][ey]&&cnt>1) puts("YES");
else{
if(mp[ex][ey]=='X'){
for(int i=1;i<=4;i++){
int tx=ex+nxt[i][0];
int ty=ey+nxt[i][1];
if(!dis[tx][ty]) cnt++;
}
if(cnt) puts("YES");
else puts("NO");
}
else puts("NO");
}
return 0;
}T6:
发现是个贪心题，但是要注意一点:
假如当前顾客已经不满意了，那么就不要给他服务了（滚蛋吧）（服务态度极差诶），因为他后面也不可能满意了。。
code:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,t[100010];
ll ans,now;
int main(){
// freopen("A.in","r",stdin);
// freopen("A.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&t[i]);
sort(t+1,t+n+1);
for(int i=1;i<=n;i++){
// printf("%d\n",now);
if(now<=t[i]) ans++;
else continue;
now+=t[i];
}
printf("%d",ans);
return 0;
}
