这次比赛打GG了。。。
T1：
根据syf教练的说法，n,m<=100，就可以直接上n^3的DP了。。
设f[i]表示前i个灯泡的放置方案数，然后我们可以得出转移方程：
f[i+k]+=f[i]，其中k是一个1~a[i]的数
首先把p和a存下来，再记录一下位置，即代码中的id
然后按照p排序一遍，然后枚举灯泡，灯座接口，还有1~a[i]，进行转移
但是要记得判断p的位置有没有重叠，重叠的话就可以break了
枚举p数组需要从大到小，不然的话可能会导致重复使用灯泡
code:
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int f[110],p[110],n,m;
struct node{
int p,a,id;
}a[110];
bool cmp(node a,node b){return a.p<b.p;}
int main(){
freopen("physics.in","r",stdin);
freopen("physics.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d%d",&a[i].p,&a[i].a),a[i].id=i;
for(int i=1;i<=m;i++)scanf("%d",&p[i]);
sort(a+1,a+n+1,cmp);
f[0]=1;
for(int i=1;i<=n;i++){
for(int j=m-1;j>=0;j--)
if(f[j]){
for(int ij=1;ij<=a[i].a;ij++){
int k=j+ij;
if(k>m) break;
if(p[k]&&p[k]!=a[i].id) break;
f[k]+=f[j];
f[k]%=mod;
}
}
}
printf("%d",f[m]==0?-1:f[m]);
return 0;
}T2:
这道题我用了10分钟就凑出来一段代码了。。
注意，是凑出来的。。。
首先仔细观察样例，找到这个轮换和置换的运算方法，然后暴力模拟。。
code
#include<bits/stdc++.h>
using namespace std;
int n,k,p,m,x,a[100010],b[100010];
vector<int> v[100010];
int main(){
freopen("rotate.in","r",stdin);
freopen("rotate.out","w",stdout);
scanf("%d%d%d",&n,&p,&k);
for(int i=1;i<=p;i++){
scanf("%d",&m);
for(int j=1;j<=m;j++)scanf("%d",&x),v[i].push_back(x);
}
for(int i=1;i<=n;i++)a[i]=i,b[i]=i;
for(int i=p;i>=1;i--)
for(int j=(int)v[i].size()-1;j>=1;j--){
swap(a[b[v[i][j]]],a[b[v[i][j-1]]]);
swap(b[v[i][j]],b[v[i][j-1]]);
}
for(int i=1;i<=n;i++)printf("%d ",a[i]);
return 0;
}T3:
这道题因为没怎么细看，导致只打了一个骗分。。。
所以还是要好好看题。。
大概就是说暴力模拟竖式除法的过程，然后用一个桶f来记录一下每次的被除数之前是否出现
如果出现，就说明有循环
这题主要是考察细节。。。
code:
#include<bits/stdc++.h>
using namespace std;
int ans,n,d,tot,f[1000010],a[1000010],cnt;
char s[1000010];
void upd(int x){
if(x<10) s[++cnt]=x+'0';
else{
upd(x/10);
s[++cnt]=x%10+'0';
}
return ;
}
int main(){
freopen("fracdec.in","r",stdin);
freopen("fracdec.out","w",stdout);
scanf("%d%d",&n,&d);
if(n%d==0){printf("%d.0",n/d);return 0;}
for(int i=1;i<=d;i++)f[i]=-1;
upd(n/d);
n%=d;
f[n]=0;
s[++cnt]='.';
while(1){
a[++ans]=n*10/d;
n=n*10%d;
if(n==0) break;
if(f[n]==-1) f[n]=ans;
else break;
}
if(n==0) for(int i=1;i<=ans;i++) upd(a[i]);
else{
for(int i=1;i<=f[n];i++) upd(a[i]);
s[++cnt]='(';
for(int i=f[n]+1;i<=ans;i++) upd(a[i]);
s[++cnt]=')';
}
for(int i=1;i<=cnt;i++){
putchar(s[i]);
if(i%76==0) puts("");
}
return 0;
}T4:
这道题是最后才做的。。。
首先手动分析样例，发现当一条边的承重z小于当前货物w的重量时，是废的
因此只需要把这些边全部给清除掉就可以了，然后判断有几个联通块（用并查集来做）
但是由于时间比较紧，所以没能想到离线排序后做，所以只有30分。。
code:
#include<bits/stdc++.h>
using namespace std;
int n,m,q,x,y,z,fa[100010],ans;
int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);}
struct node{
int x,y,z;
}a[100010];
struct e{
int x,y;
}w[100010];
bool cmp(node x,node y){return x.z>y.z;}
bool cmp1(e x,e y){return x.x>y.x;}
bool cmp2(e x,e y){return x.y<y.y;}
int main(){
freopen("warehouse.in","r",stdin);
freopen("warehouse.out","w",stdout);
scanf("%d%d%d",&n,&m,&q);
ans=n;
for(int i=1;i<=m;i++)scanf("%d%d%d",&x,&y,&z),a[i]=(node){x,y,z};
for(int i=1;i<=q;i++)scanf("%d",&w[i].x),w[i].y=i;
for(int i=1;i<=n;i++)fa[i]=i;
sort(w+1,w+q+1,cmp1);
sort(a+1,a+m+1,cmp);
int now=1;
for(int i=1;i<=q;i++){
while(a[now].z>=w[i].x){
int fx=getfa(a[now].x),fy=getfa(a[now].y);
if(fx!=fy) fa[fx]=fy,ans--;
now++;
}
w[i].x=ans;
}
sort(w+1,w+q+1,cmp2);
for(int i=1;i<=q;i++)printf("%d\n",w[i].x);
return 0;
}T5：
首先得出一个结论：
1.数越多，and值单调递减
2.数越多，or值单调递增
然后就可以固定右端点r,二分出最大的满足条件的左端点l,再二分出最小的满足条件的l,相减+1即可得到答案（因为单调）
然后判断是否合法可以用st表或者线段树来实现，但是这题常数很大，推荐st表
然而我还是写了线段树。。。用了inline、read、print还有线段树区间l,r赋为全局变量来卡常，终于险A：
code:
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,a,b,c,len,d,s[100010],l,r,MAPLE,l1,r1;
struct node{
int cor,cand,lc,rc,l,r;
}tr[500010];
inline int ask_or(int now){
if(tr[now].l>=l1&&tr[now].r<=r1) return tr[now].cor;
int mid=tr[now].l+tr[now].r>>1;
if(mid>=r1) return ask_or(tr[now].lc);
else if(mid<l1) return ask_or(tr[now].rc);
else return ask_or(tr[now].lc)|ask_or(tr[now].rc);
}
inline void build_tree(int l,int r){
len++;int now=len;
tr[now].l=l,tr[now].r=r;
if(l==r){tr[now].cor=tr[now].cand=s[l];return ;}
int mid=l+r>>1;
tr[now].lc=len+1;build_tree(l,mid);
tr[now].rc=len+1;build_tree(mid+1,r);
tr[now].cand=tr[tr[now].lc].cand&tr[tr[now].rc].cand;
tr[now].cor=tr[tr[now].lc].cor|tr[tr[now].rc].cor;
return ;
}
inline int ask_and(int now){
if(tr[now].l>=l1&&tr[now].r<=r1) return tr[now].cand;
int mid=tr[now].l+tr[now].r>>1;
if(mid>=r1) return ask_and(tr[now].lc);
else if(mid<l1) return ask_and(tr[now].rc);
else return ask_and(tr[now].lc)&ask_and(tr[now].rc);
}
inline void read(int &x){
char ch=getchar();
while(!isdigit(ch)) ch=getchar();
x=0;while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
}
void print(int x){
if(x<10) putchar(x+'0');
else{
print(x/10);
putchar(x%10+'0');
}
}
int main(){
freopen("range.in","r",stdin);
freopen("range.out","w",stdout);
read(n);read(a);read(b);read(c);read(d);
for(int i=1;i<=n;i++)read(s[i]);
build_tree(1,n);
for(int i=1;i<=n;i++){
int r=i,l=1,ans=0;
while(l<=r){
int mid=l+r>>1;
l1=mid;r1=i;
int t=ask_and(1);
int k=ask_or(1);
if(t<=b&&k>=c) l=mid+1,ans=mid;
else r=mid-1;
}
l=1;
int cnt=ans;ans=i+1;
r=i;
while(l<=r){
int mid=l+r>>1;
l1=mid;
r1=i;
int t=ask_and(1);
int k=ask_or(1);
if(t>=a&&k<=d) r=mid-1,ans=mid;
else l=mid+1;
}
if(cnt-ans+1>0) MAPLE+=cnt-ans+1;
MAPLE%=mod;
}
print(MAPLE%mod);
return 0;
}T6:
专门为XMR爸爸准备的题啊。。。
我只理概念：
期望：
对于每种概率，乘上这种可能的值，他们的和就是期望
