T1 考场上暴力打炸了 ，注意n<=100 用Floyd O（n^3）即可
#include<bits/stdc++.h>
using namespace std;
int main(){
freopen("count.in","r",stdin);
freopen("count.out","w",stdout);
int f[101][101],n,m,p;
cin>>n>>m;
memset(f,INT_MAX/INT_MAX,sizeof(f));
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
f[a][b]=1;
f[b][a]=1;
}
T2看到子任务捆绑测试，且无思路 直接骗分 65分代码：
#include<bits/stdc++.h>
using namespace std;
int to[1000001],un[1000001];
int main(){
freopen("puzzle.in","r",stdin);
freopen("puzzle.out","w",stdout);
int idx,n;
char s[1000001];
cin>>idx>>n>>s+1;
if(n<=2){
cout<<0;
return 0;
}
if(idx==5){
if(n==3){
cout<<1;
return 0;
}
long long ans=2,op=2;
for(int i=4;i<=n;i++){
if(i==4){
continue;
}
if(i%2==1){
ans+=op;
}
if(i%2==0){
ans+=op;
op++;
}
}
cout<<ans;
return 0;
}
if(idx<=3){
long long ans=0;
to[1]=INT_MAX;
un[n]=INT_MAX;
for(int i=1;i<=n;i++){
for(int j=i-1;j>=1;j--){
if(s[j]=='1'){
to[i]=j;
break;
}
if(j==1){
to[i]=0;
}
}
for(int j=i+1;j<=n;j++){
if(s[j]=='1'){
un[i]=j;
break;
}
if(j==n){
un[i]=n+1;
}
}
}
un[n]=n+1;
to[1]=0;
for(int i=2;i<=n-1;i++){
if(s[i]!='1'){
continue;
}
int left=i,right=i,left1,right1,l=0;
while(left!=0&&right!=n+1){
left1=left;
right1=right;
left=to[left];
right=un[right];
if(l==0){
ans+=((right-right1-1)*(left1-left-1));
}
if(l>0){
ans+=((right-right1)*(left1-left));
}
l++;
}
}
cout<<ans;
return 0;
}
if(idx==4){
int t1=0,t2=n+1;
long long ans=0;
for(int i=1;i<=n;i++){
if(s[i]=='1'){
to[i]=t1;
t1=i;
}
else{
to[i]=t1;
}
}
for(int i=n;i>=1;i--){
if(s[i]=='1'){
un[i]=t2;
t2=i;
}
else{
un[i]=t2;
}
}
un[n]=n+1;
to[1]=0;
for(int i=2;i<=n-1;i++){
if(s[i]!='1'){
continue;
}
int left=i,right=i,left1,right1,l=0;
while(left!=0&&right!=n+1){
left1=left;
right1=right;
left=to[left];
right=un[right];
if(l==0){
ans+=((right-right1-1)*(left1-left-1));
}
if(l>0){
ans+=((right-right1)*(left1-left));
}
l++;
}
}
cout<<ans;
return 0;
}
cout<<1;
return 0;
}
T3 考试时代码一直时间超限，都是1005ms，不会优化常数项，没改出来 超时代码
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
long long w[100001];
struct Money{
int v,x;
};
map <long long,long long> mm;
struct Money a[100001];
bool cmp(struct Money a1,struct Money a2){
if(a1.v>a2.v){
return 0;
}
else{
return 1;
}
}
int main(){
freopen("present.in","r",stdin);
freopen("present.out","w",stdout);
int n,m,jj=1;
cin>>n>>m;
for(int i=1;i<=n;i++){
unsigned long long s1,s2;
scanf("%lld",&s1);
scanf("%lld",&s2);
if(mm[s1]>0){
a[mm[s1]].x+=s2;
jj++;
continue;
}
a[i].v=s1;
mm[s1]=i;
a[i].x=s2;
}
sort(a+1,a+n+1,cmp);
//for(int i=jj;i<=n;i++){
// cout<<a[i].v<<" "<<a[i].x<<endl;
//}n=jj;return 0;
for(int i=1;i<=m;i++){
scanf("%lld",&w[i]);
unsigned long long ans=0,ly,right=n;
while(w[i]>=a[jj].v){
long long left=jj,p=0;
while(left<=right){
if(left==right){
if(a[left].v>w[i]){
p=0;
}
else{
p=left;
}
break;
}
int mid=(left+right)/2;
if(a[mid].v>w[i]){
right=mid-1;
}
if(a[mid].v<w[i]){
if(a[mid+1].v>w[i]){
p=mid;
break;
}
left=mid+1;
}
if(a[mid].v==w[i]){
p=mid;
break;
}
}
if(p==0){
break;
}
right=p-1;
ly=w[i]/a[p].v;
if(ly==0){
break;
}
if(ly<=a[p].x){
ans+=ly;
w[i]-=(a[p].v*ly);
continue;
}
ans+=a[p].x;
w[i]-=(a[p].v*a[p].x);
}
cout<<ans<<endl;
}
return 0;
}