版权原因，题目不公开。
DEC
把(A-B=C)的条件转化为(A=B+C)，每个数映射到(map)里面，完事再过一遍看加上(C)是否出现。注意映射到(int)并记录个数，这样才符合题意（不同位置算不同组）。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[500010];
map<ll,int> m;
inline int read()
{
int 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<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x*f;
}
int main()
{
freopen("dec.in","r",stdin);
freopen("dec.out","w",stdout);
ll n,c;
scanf("%lld%lld",&n,&c);
for(int i=1;i<=n;i++)
{
a[i]=read();
m[a[i]]++;
}
ll ans=0;
for(int i=1;i<=n;i++)
ans+=m[a[i]+c];
printf("%lld
",ans);
return 0;
}
CARGO
水。二进制扫一遍进位就完了。
#include<bits/stdc++.h>
using namespace std;
int v[2000010];
inline int read()
{
int 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<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x*f;
}
int main()
{
freopen("cargo.in","r",stdin);
freopen("cargo.out","w",stdout);
int n,ans=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int a=read();
v[a]++;
}
for(int i=0;i<=1000005;i++)
{
v[i+1]+=(v[i]/2);
v[i]%=2;
if(v[i])ans++;
}
printf("%d
",ans);
return 0;
}
FISH
考试时没看懂题...
看懂了其实挺简单，维护一个栈来模拟。0就放进栈，1就把里面比它小的都吃掉。如果吃空了累计起来，这条鱼会存活。
最后的答案就是栈的size加上吃空栈的鱼。
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int 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<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x*f;
}
stack<int> s;
int main()
{
int n=read(),ans=0;
for(int i=1;i<=n;i++)
{
int a=read(),b=read();
if(b)s.push(a);
else
{
while(!s.empty()&&s.top()<a)s.pop();
if(s.empty())ans++;
}
}
printf("%d
",ans+s.size());
return 0;
}
PROGRAM
稍微找找规律。
发现(lfloor frac{a+b}{a*b} floor)的值在(a>2,b>2)时恒为0。
并且当(a,b)有一个值为1的时候，就会对答案贡献1。
如果(a,b)两个都是1，就会贡献2。
特殊地，两个2也会对答案贡献1。
那么答案就是1的个数乘上((n-1))再加上(c*(c-1)/2)(c为2出现的次数)，因为每两个2都会对答案贡献1。
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
int 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<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x*f;
}
signed main()
{
freopen("program.in","r",stdin);
freopen("program.out","w",stdout);
int n=read(),ans=0;
int cnt_2=0;
for(int i=1;i<=n;i++)
{
int q=read();
if(q==2)cnt_2++;
if(q==1)ans+=(n-1);
}
printf("%lld
",ans+(cnt_2*(cnt_2-1)/2));
return 0;
}
DISH
发现每一层有效的宽度为(min{a[i-1],q})。于是就得到了一个单调递减的序列(a[])。
二分找一下每个圆盘能放下的位置。然后模拟就完了。
#include<bits/stdc++.h>
using namespace std;
const int INF=1e9;
int a[100010]={INF};
int n;
int ef(int x)
{
int l=1,r=n;
int m=l+r>>1;
while(l!=r)
{
if(a[m]>=x)l=m+1;
else r=m;
m=l+r>>1;
}
return m;
}
int main()
{
int m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int q;
scanf("%d",&q);
a[i]=min(a[i-1],q);
}
int top=n,cnt=0;//从上至下分为1-n
while(m--)
{
int q;
scanf("%d",&q);
top=min(top-1,ef(q)-1);
if(top<1)
break;
cnt++;
}
printf("%d
",cnt==n-1?n:cnt);
return 0;
}
PERM
最后一题晚点补qaq