前几天感冒了三天没怎么写题。。。今天好很多了打个三星场找点手感。
不行啊我好菜啊。只会8个。。补题的话，再说吧。G题感觉值得一补。
补了G，K不想写B不会。
说实话这个三星场还是很新人向的，知识点也蛮多(
A:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+;
string s,t;
ll ans[];
int main(){
ios::sync_with_stdio(false);
cin>>s>>t;
int n=s.length(),m=t.length();
s="*"+s;t="*"+t;
ans[]=;
for(int i=;i<=n;i++){
for(int j=m;j>=;j--){
if(s[i]==t[j]){
ans[j]=(ans[j]+ans[j-])%mod;
}
}
}
cout<<ans[m]<<endl;
}
B：咕咕咕
C：援圆交，注意两圆相切
#include <bits/stdc++.h>
using namespace std;
typedef double db;
const db eps=1e-;
const db pi=acos(-);
int sign(db k){
if (k>eps) return ; else if (k<-eps) return -; return ;
}
int cmp(db k1,db k2){return sign(k1-k2);}
struct point{
db x,y;
point operator + (const point &k1) const{return (point){k1.x+x,k1.y+y};}
point operator - (const point &k1) const{return (point){x-k1.x,y-k1.y};}
point operator * (db k1) const{return (point){x*k1,y*k1};}
point operator / (db k1) const{return (point){x/k1,y/k1};}
int operator == (const point &k1) const{return cmp(x,k1.x)==&&cmp(y,k1.y)==;}
bool operator < (const point k1) const{
int a=cmp(x,k1.x);
if (a==-) return ; else if (a==) return ; else return cmp(y,k1.y)==-;
}
db abs(){return sqrt(x*x+y*y);}
db abs2(){return x*x+y*y;}
point turn(db k1){return (point){x*cos(k1)-y*sin(k1),x*sin(k1)+y*cos(k1)};}
point turn90(){return (point){-y,x};}
point unit(){db w=abs(); return (point){x/w,y/w};}
db dis(point k1){return ((*this)-k1).abs();}
void print(){printf("%.11lf %.11lf\n",x,y);}
};
struct circle{
point o;db r;
int inside(point k){return cmp(r,o.dis(k));}
};
int checkposCC(circle k1,circle k2){// 返回两个圆的公切线数量
if (cmp(k1.r,k2.r)==-) swap(k1,k2);
db dis=k1.o.dis(k2.o); int w1=cmp(dis,k1.r+k2.r),w2=cmp(dis,k1.r-k2.r);
if (w1>) return ; else if (w1==) return ; else if (w2>) return ;
else if (w2==) return ; else return ;
}
vector<point> getCC(circle k1,circle k2){// 沿圆 k1 逆时针给出 , 相切给出两个
int pd=checkposCC(k1,k2); if (pd==||pd==) return {};
db a=(k2.o-k1.o).abs2(),cosA=(k1.r*k1.r+a-k2.r*k2.r)/(*k1.r*sqrt(max(a,(db)0.0)));
db b=k1.r*cosA,c=sqrt(max((db)0.0,k1.r*k1.r-b*b));
point k=(k2.o-k1.o).unit(),m=k1.o+k*b,del=k.turn90()*c;
return {m-del,m+del};
}
point a,b;db d;
set<point>st;
int main(){
//db delta = rand()/65536;
scanf("%lf%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y,&d);
//a.turn(delta),b.turn(delta);
circle x = {a,d},y={b,a.dis(b)};
vector<point> s = getCC(x,y);
if(s.empty()){
printf("NO\n");
}else{
for(auto tmp:s){
st.insert(tmp);
}
if(st.size()==){
printf("NO\n");
return ;
}
printf("YES\n");
for(auto tmp:st){
tmp.print();
}
}
}
D：被这题烦死了。
#include <bits/stdc++.h>
using namespace std;
int n,m,t;char p[];
int main(){
scanf("%d%d%d",&n,&m,&t);
int mx1=,mn1=,mx2=,mn2=,x=,y=;
for(int i=;i<=t;i++){
scanf("%s",p);
if(p[]=='D'){
y++;
}else if(p[]=='B'){
x--;
}else if(p[]=='C'){
x++;
}else if(p[]=='E'){
y--;
}
mx1=max(mx1,x);
mn1=min(mn1,x);
mx2=max(mx2,y);
mn2=min(mn2,y);
}
int h=mx2-mn2+,w=mx1-mn1+;
h=m-h,w=n-w;
x-=mn1,y-=mn2;
printf("%d\n",(w+)*(h+));
for(int i=x;i<=x+w;i++){
for(int j=y;j<=y+h;j++){
printf("%d %d\n",i+,j+);
}
}
}
E：哇根本不可做啊！！！被治了四个小时啊。
#include <bits/stdc++.h>
using namespace std;
int dp[][];
char s[];int k;
int main(){
scanf("%s%d",s+,&k);
int n = strlen(s+);
for(int l=;l<=n;l++){
for(int i=;i<=n;i++){
if(i+l>n)break;
dp[i][i+l]=dp[i+][i+l-]+(s[i]==s[i+l]?:);
}
}
int ans = ;
for(int i=;i<=n;i++){
for(int j=i;j<=n;j++){
if(dp[i][j]<=k)
ans++;
}
}
printf("%d\n",ans);
}
F：最短路
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e4+;
struct Edge{int v;ll w;int nxt;};
Edge e[];
int head[N],cnt=;
void addEdge(int u,int v,ll w){
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].nxt=head[u];
head[u]=cnt;
}
int n,c,m;
ll dis[N];
struct node{
ll u,d;
bool operator <(const node&rhs) const{
return d>rhs.d;
}
};
void Dijkstra(){
for(int i=;i<=n;i++)dis[i]=1e18;
dis[]=;
priority_queue<node> Q;
Q.push((node){,});
while (!Q.empty()){
node fr = Q.top();Q.pop();
ll u = fr.u,d=fr.d;
if(d>dis[u])continue;
for(int i=head[u];i;i=e[i].nxt){
ll v=e[i].v,w=e[i].w;
if(dis[u]+w<dis[v]) {
dis[v] = dis[u] + w;
Q.push((node) {v, dis[v]});
}
}
}
}
ll t,k,p,vis[N],x,y,z;
int main(){
ios::sync_with_stdio(false);
cin>>n>>m>>t>>k>>p;
for(int i=;i<=p;i++){
cin>>x;vis[x]=;
}
for(int i=;i<=m;i++){
cin>>x>>y>>z;
if(vis[y])addEdge(x,y,z*+k);
else addEdge(x,y,z*);
}
Dijkstra();
if(dis[n]<=t*){
cout<<dis[n]<<endl;
}else{
cout<<-<<endl;
}
}
G：没看懂样例。
考虑主人坐在0号位置，然后我们枚举第一个人坐在哪。那么剩下的就相当于res个凳子放c-1个人每两个人中间至少有r个凳子。
去年青岛有个一样的。学长讲过但是我当时记不清了。。。 我们先把凳子放好，然后就变成 剩下的凳子放入c个桶里了。
注意会爆int和数组开两倍。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+;
const ll mod = 1e9+;
ll up[N<<],inv[N<<],down[N<<];
void init(){
up[]=;
for(int i=;i<=;i++){
up[i]=up[i-]*i%mod;
}
inv[]=;
for(int i=;i<=;i++){
inv[i]=(mod-mod/i)*inv[mod%i]%mod;
}
down[]=;
for(int i=;i<=;i++){
down[i]=down[i-]*inv[i]%mod;
}
}
ll C(ll x,ll y){
return up[x]*down[y]%mod*down[x-y]%mod;
}
int n,c,r;
int main(){
init();
scanf("%d%d%d",&n,&c,&r);
ll ans = ;
for(int i=;i<n;i++){
ll res = n--(i+r+)+;
res+=min(,i-r);
res-=1ll*r*(c-);
res-=c-;
if(res<)continue;
ans=(ans+C(res+c-,c-))%mod;
}
ans=ans*n%mod;
if(ans) cout<<ans<<endl;
else cout<<-<<endl;
}
H：又一个最短路。。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+;
struct Edge{int v,w,nxt;};
Edge e[N*];
int head[N],cnt=;
void addEdge(int u,int v,int w){
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].nxt=head[u];
head[u]=cnt;
}
int n,c,m;
int dis[N],vis[N];
struct node{
int u,d;
bool operator <(const node&rhs) const{
return d>rhs.d;
}
};
void Dijkstra(){
for(int i=;i<=n;i++)dis[i]=1e8;
dis[]=vis[];
priority_queue<node> Q;
Q.push((node){,vis[]});
while (!Q.empty()){
node fr = Q.top();Q.pop();
int u = fr.u,d=fr.d;
if(d>dis[u])continue;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(dis[u]+w<dis[v]) {
dis[v] = dis[u] + w;
Q.push((node) {v, dis[v]});
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>c>>m;int x,y;
for(int i=;i<=c;i++){
cin>>x;vis[x]=;
}
for(int i=;i<=m;i++){
cin>>x>>y;
if(vis[y])addEdge(x,y,);
else addEdge(x,y,);
}
Dijkstra();
cout<<dis[n]<<' ';
for(int i=;i<=cnt;i++){
e[i].w=-e[i].w;
}
vis[]=-vis[];
Dijkstra();
cout<<-dis[n];
}
I：显然是矩阵快速幂。瞎搞一番一千点！之后猛然发现，，你根本不用构造矩阵，给你的就是吧。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+;
void exgcd(ll a,ll b,ll& d,ll& x,ll& y) {
if (!b) {
d = a;
x = ;
y = ;
} else {
exgcd(b, a % b, d, y, x);
y -= x * (a / b);
}
}
ll inv(ll a, ll p) {
ll d, x, y;
exgcd(a, p, d, x, y);
return d == ? (x+p)%p : -;
}
int n,k;
struct mat{
ll v[][];
mat(){
memset(v,, sizeof(v));
}
};
mat mul(mat &a,mat &b){
mat c;
for(int i=;i<n;i++){
for(int j=;j<n;j++){
for(int k=;k<n;k++){
c.v[i][j] = (c.v[i][j]+a.v[i][k]*b.v[k][j])%mod;
}
}
}
return c;
}
mat pow(mat a, int x){
mat b;
for(int i=;i<n;i++)
b.v[i][i]=;
while (x>){
if(x&)
b = mul(b,a);
a = mul(a,a);
x>>=;
}
return b;
}
int main(){
scanf("%d%d",&n,&k);
mat a;ll tmp;
for(int i=;i<n;i++){
for(int j=;j<n;j++){
scanf("%lld",&tmp);
tmp = tmp*inv(,mod)%mod;
a.v[i][j]=tmp;
}
}
mat b = pow(a,k);
ll ans = ;
for(int i=;i<n;i++){
ans=(ans+1ll*(i+)*b.v[][i])%mod;
}
printf("%lld\n",ans);
}
J：二分，然后我们找c最小的。nlognlogn竟然这么快么。。。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Node{
ll a,b,c;
bool operator <(const Node &t)const {
return c>t.c;
}
}p[];
int n;ll k;
bool check(ll x,ll k){
priority_queue<Node> q;
for(int i=;i<=n;i++){
if(p[i].a<x)q.push(p[i]);
}
for(int i=;i<=n;i++){
if(p[i].a>x){
ll tmp = p[i].a,all=;
while (tmp>x&&!q.empty()){
Node y = q.top();q.pop();
if(tmp-x>=x-y.a){
tmp-=(x-y.a);
all+=(x-y.a)*(p[i].b+y.c);
}else{
y.a+=(tmp-x);
all+=(tmp-x)*(p[i].b+y.c);
tmp=x;
q.push(y);
}
}
k-=all;
if(tmp>x||k<)return false;
}
}
return true;
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>k;
ll sum = ,mx=;
for(int i=;i<=n;i++){
cin>>p[i].a>>p[i].b>>p[i].c;
sum+=p[i].a;mx=max(mx,p[i].a);
}
ll l=sum/n,r=mx,ans;
while (l<=r){
ll mid = l+r>>;
if(check(mid,k)){
r=mid-;
ans=mid;
}else{
l=mid+;
}
}
cout<<ans<<endl;
}
/**
5 2
5 3 8
2 8 3
3 2 4
7 2 1
6 1 1 */
K：对字符串一窍不通。反正队友什么都会