啊今天有点挂机啊
D题和队友暴力后发现一组数据跑得飞快
然后遇上1e5组数据就没了.....
然后我疯狂优化暴力
然后去世了
最后半小时F也没写出来
主要还是最后有点慌并且没有考虑清楚
导致情况越写越多最后写了23个if
这肯定是完蛋了啊
A:签到
#include <bits/stdc++.h>
#define int long long
typedef long long ll;
using namespace std;
const int N = 2e5 + 10;
int n, a[N];
void ss() {
cin >> n;
for (int i = 1; i <= n; i++)cin >> a[i];
sort(a + 1, a + 1 + n);
int ans = 0;
for (int i = 1; i <= n / 2; i++) ans += a[n - i + 1] - a[i];
cout << ans << endl;
}
int32_t main() {
ios::sync_with_stdio(0), cin.tie(0);
int T;
cin >> T;
while (T--)ss();
}
View Code
B:签到
#include<iostream>
#include<cstdio>
#define MAXN 100005
#define ll long long
using namespace std;
int n;
ll a[MAXN];
int solve(){
int l = 1, r = n, cnt = 0;
ll lsum = 0, rsum = 0;
if (n == 1) return 0;
while (l <= r) {
if (lsum < rsum) {
++cnt;
lsum += a[l++];
}
else if (lsum > rsum) {
++cnt;
rsum += a[r--];
}
else {
lsum = a[l++];
rsum = a[r--];
}
}
if (lsum != rsum) ++ cnt;
return cnt;
}
void input(){
int T;
scanf("%d", &T);
while (T--){
scanf("%d", &n);
for (int i = 1; i <= n;++i){
scanf("%d", &a[i]);
}
int ans = solve();
printf("%d\n", ans);
}
}
int main(){
input();
return 0;
}
View Code
C:交互题 贪心的贴墙走
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int x, y;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
char iin[60];
char* str[] = {"DOWN", "RIGHT", "UP", "LEFT"};
bool judge(int nx, int ny, int dir){
if (!x || !y) {
return 0;
}
cout << "LOOK " << str[dir] << endl;
cin >> iin;
return !strcmp(iin, "SAFE");
}
void input(){
int dir = 1;
x = y = 1;
while (true) {
dir = (dir+3) % 4;
while (!judge(x+dx[dir], y+dy[dir], dir)) {
dir = (dir+1) % 4;
}
x += dx[dir];
y += dy[dir];
cout << "GO " << str[dir] << endl;
cin >> iin;
if (!strcmp(iin, "YES")) {
break;
}
}
}
int main(){
input();
return 0;
}
View Code
D:
一开始想的暴力是我暴力分解N 把它分解成一些数的乘积
那么这些数可以作为某个ans的质因数指数
在选取质因子 再去重复
然后t的死死的
在这个思路上挣扎了1小时之后投了 扔给队友
幸好最后一小时队友找到了简单解法
对于一个ans 把他分解为p1^a1*p2^a2*...*pm^am
那么有(a1+1)(a2+1)*...*(am+1)==n
对n分解为p1^b1*p2^b2*...*pk^bk
对于b1个p1 把他分配到m个括号中
设第i个括号分了ci 有 c1+c2+...+cm=b1
简单的组合数问题
同理 p2 pk也是 最后乘起来
这样就很巧妙的避免了重复
因为就算某两个括号的值相同
但是他们是作为两个不同的素数的指数
ans之间一定不同 故不重复
#include <bits/stdc++.h>
#define int long long
#pragma GCC optimize(3)
#define endl "\n"
typedef long long ll;
using namespace std;
ll mod = 1e9 + 7;
int n, m;
vector<int> tmp;
map<int, map<int, int> > PP;
int f[100000];
int f1[110];
ll ans;
ll qpow(ll a, ll n) {
ll ans = 1;
for (; n; n >>= 1, a = a * a % mod) if (n & 1) ans = ans * a % mod;
return ans;
}
vector<int> c;
void get(int n) {
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
int cnt = 0;
while (n % i == 0)n /= i, cnt++;
c.push_back(cnt);
}
}
if (n > 1)c.push_back(1);
}
int C(int n, int m) {
if (m > n)return 0;
int res = 1;
for (int i = n; i >= n - m + 1; i--) {
res = (res * i) % mod;
}
return res * f1[m] % mod;
}
void ss() {
cin >> n >> m;
c.clear();
int ans = 1;
get(n);
for (auto p:c) {
ans = (ans * C(m + p - 1, p)) % mod;
}
cout << ans << endl;
}
int32_t main() {
ios::sync_with_stdio(0), cin.tie(0);
f1[0] = 1;
for (int i = 1; i <= 100; i++) f1[i] = 1LL * f1[i - 1] * i % mod;
for (int i = 1; i <= 100; i++) f1[i] = qpow(f1[i], mod - 2);
int T;
cin >> T;
while (T--)ss();
}
View Code
E:签到题
#include<cstdio>
using namespace std;
int T,n,m;
int main(){
scanf("%d",&T);
while(T--){
int u,v,falg=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&u,&v);
if(u==1&&v==n)falg=1;
}
if(falg)printf("Jorah Mormont\n");
else printf("Khal Drogo\n");
}
return 0;
}
View Code
F:
一开始的思路是,按A矩阵的长宽离散坐标系并把A平移到原点
然后考虑A平移后和B相交的情况
四个角 四个角附近的8个格子 B过坐标轴的四个各自 四个角向内部走一个的四个格子.....
然后就没了
这题就属于没想好就开始摸键盘 一开始大体想的情况很少 然后写的过程中打补丁
然后就乱了
比较简洁的做法也有很多
G:数位DP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll T,L,R,A,B,f[100][2][2][2][2];
ll Dfs(ll now,ll okx1,ll okx2,ll oky,ll okz){
if(now<0)return 0;
if(f[now][okx1][okx2][oky][okz]!=-1)return f[now][okx1][okx2][oky][okz];
ll xl=0,xr=1,yl=0,yr=1,zl=0,zr=1;
if(okx1)xl=(L>>now)&1;
if(okx2)xr=(R>>now)&1;
if(oky)yr=(A>>now)&1;
if(okz)zr=(B>>now)&1;
ll res=0;
for(ll i=xl;i<=xr;i++)
for(ll j=yl;j<=yr;j++)
for(ll k=zl;k<=zr;k++){
ll tis=((i^j)+(j&k)+(k^i))*(1ll<<now);
res=max(res,tis+Dfs(now-1,okx1&&i==xl,okx2&&i==xr,oky&&j==yr,okz&&k==zr));
}
return f[now][okx1][okx2][oky][okz]=res;
}
int main(){
scanf("%lld",&T);
while(T--){
memset(f,-1,sizeof(f));
scanf("%lld%lld%lld%lld",&L,&R,&A,&B);
printf("%lld\n",Dfs(62,1,1,1,1));
}
return 0;
}
View Code
H:二分+几何
平移到原点之后 在能和x正半轴产生交点的边中 交点横坐标和距离原点的距离(凸包上逆时针距离几个点)是有单调性的
二分
最后其实不用平移旋转每个点 只需要把x=k这个线挪动就好了
#include<bits/stdc++.h>
#define db double
#define Vector Point
#define maxn 100010
using namespace std;
struct Point{
db x,y;
Point(db X=0,db Y=0){x=X;y=Y;}
};
Vector operator + (Vector A,Vector B){return Vector(A.x+B.x,A.y+B.y);}
Vector operator - (Vector A,Vector B){return Vector(A.x-B.x,A.y-B.y);}
Vector operator * (Vector A,db p){return Vector(A.x*p,A.y*p);}
Vector operator / (Vector A,db p){return Vector(A.x/p,A.y/p);}
bool operator < (const Point &a,const Point &b){
return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
const db eps=1e-10;
int dcmp(db x){
if(fabs(x)<eps)return 0;
else return x<0?-1:1;
}
bool operator ==(const Point &a,const Point &b){
return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;
}
db Dot(Vector A,Vector B){return A.x*B.x+A.y*B.y;}//A B 点积
db Length(Vector A){return sqrt(Dot(A,A));}//向量长度
db Angle(Vector A,Vector B){return acos(Dot(A,B)/Length(A)/Length(B));}//A B 夹角
db Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}//A B 叉积
db Area2(Point A,Point B,Point C){return Cross(B-A,C-A);}//A B 构成的平行四边形面积2倍
Vector Rotate(Vector A,db rad){//A逆时针旋转rad
return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));
}
Vector Normal(Vector A){//返回A的单位法向量
return Vector(-A.y/Length(A),A.x/Length(A));
}
//点和直线
Point GetLineIntersection(Point P,Vector v,Point Q,Vector w){//返回直线P+tv Q+tw的交点
Vector u=P-Q;
db t=Cross(w,u)/Cross(v,w);
return P+v*t;
}
db DistanceToLine(Point P,Point A,Point B){//P到直线AB的距离
Vector v1=B-A,v2=P-A;
return fabs(Cross(v1,v2)/Length(v1));
}
db DistanceToSegment(Point P,Point A,Point B){//P到线段AB的距离
if(A==B)return Length(P-A);
Vector v1=B-A,v2=P-A,v3=P-B;
if(dcmp(Dot(v1,v2))<0)return Length(v2);
else if(dcmp(Dot(v1,v3))>0)return Length(v3);
else return fabs(Cross(v1,v2))/Length(v1);
}
Point GetLineProjection(Point P,Point A,Point B){//P在直线AB上的投影
Vector v=B-A;
return A+v*(Dot(v,P-A)/Dot(v,v));
}
//bool isSL(Point p1,Point p2,Point q1,Point q2){//判断直线p1p2和线段q1q2有无交点(不严格)
// return dcmp(Cross(p2-p1,q1-p1)*Cross(p2-p1,q2-p1))!=1;
//}
//bool isSL_s(Point p1,Point p2,Point q1,Point q2){//判断直线p1p2和线段q1q2有无交点(严格)
// return dcmp(Cross(p2-p1,q1-p1)*Cross(p2-p1,q2-p1))==-1;
//}
int isLL(Point k1,Point k2,Point k3,Point k4){// 求直线 k1,k2 和 k3,k4 的交点
return dcmp(Cross(k3-k1,k4-k1)-Cross(k3-k2,k4-k2))!=0;
}
Point getLL(Point k1,Point k2,Point k3,Point k4){
db w1=Cross(k1-k3,k4-k3),w2=Cross(k4-k3,k2-k3); return (k1*w2+k2*w1)/(w1+w2);
}
bool intersect(db l1,db r1,db l2,db r2){
if(dcmp(l1-r1)==1)swap(l1,r1);if(dcmp(l2-r2)==1)swap(l2,r2);
return !(dcmp(r1-l2)==-1||dcmp(r2-l1)==-1);
}
bool isSS(Point p1,Point p2,Point q1,Point q2){
return intersect(p1.x,p2.x,q1.x,q2.x)&&intersect(p1.y,p2.y,q1.y,q2.y)&&
dcmp(Cross(p2-p1,q1-p1)*Cross(p2-p1,q2-p1))!=1&&
dcmp(Cross(q2-q1,p1-q1)*Cross(q2-q1,p2-q1))!=1;
}
bool isSS_s(Point p1,Point p2,Point q1,Point q2){
return dcmp(Cross(p2-p1,q1-p1)*Cross(p2-p1,q2-p1))==-1
&&dcmp(Cross(q2-q1,p1-q1)*Cross(q2-q1,p2-q1))==-1;
}
db Area(vector<Point> A){ // 多边形用 vector<point> 表示 , 逆时针 求面积
db ans=0;
for (int i=0;i<A.size();i++) ans+=Cross(A[i],A[(i+1)%A.size()]);
return ans/2;
}
int n,Q;
Point p[maxn];
bool Judge(int pl,int pr,int dis,int k){
int a=(pr+dis)%n;
int b=(a+1)%n;
Point ins=getLL(p[a],p[b],p[pl],p[pr]);
return dcmp(Length(ins-p[pl])-Length(ins-p[pr]))>0&&dcmp(Length(ins-p[pl])-k)<=0;
}
bool Check(int pl,int pr,int b,int k){
int a=(b-1+n)%n;
Point ins=getLL(p[a],p[b],p[pl],p[pr]);
return dcmp(Length(ins-p[pl])-k)==0;
}
int main(){
scanf("%d%d",&n,&Q);
for(int i=0;i<n;i++){
scanf("%lf%lf",&p[i].x,&p[i].y);
}
int pl,pr,k,ans=-1;
while(Q--){
scanf("%d%d",&pl,&k);pr=(pl+1)%n;
int l=0,r=n-1;
while(l<=r){
int mid=(l+r)/2;
if(Judge(pl,pr,mid,k)){
ans=(pr+mid+1)%n;l=mid+1;
}
else r=mid-1;
}
if(Check(pl,pr,ans,k))printf("%d %d\n",(ans-1+n)%n,ans);
else printf("%d\n",ans);
}
return 0;
}
/*
7 3
5 5
2 6
0 5
-1 3
0 0
6 0
6 3
4 7
4 8
4 10000
7 3
5 4
2 5
0 4
-1 2
0 0
6 0
6 2
4 7
4 8
4 10000
*/
View Code
L:矩阵优化最短路dp
#include <bits/stdc++.h>
#define int long long
typedef long long ll;
using namespace std;
const int MT = 200;
int n, m, k;
ll mod = 1e9 + 7;
ll inf = 3e18;
struct Matrix {
pair<int, int> v[MT][MT];
void init() {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
v[i][j] = {inf, 0};
}
Matrix operator*(const Matrix B) const {
Matrix C;
C.init();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
if (v[i][k].first + B.v[k][j].first < C.v[i][j].first) {
C.v[i][j].first = v[i][k].first + B.v[k][j].first;
}
}
for (int k = 1; k <= n; k++) {
if (v[i][k].first + B.v[k][j].first == C.v[i][j].first) {
(C.v[i][j].second += v[i][k].second * B.v[k][j].second) %= mod;
}
}
}
}
return C;
}
} mp;
int32_t main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m >> k;
mp.init();
while (m--) {
int u, v, w;
cin >> u >> v >> w;
mp.v[u][v] = {w, 1};
mp.v[v][u] = {w, 1};
}
Matrix ans = mp;
k--;
for (; k; k >>= 1, mp = mp * mp) if (k & 1) ans = ans * mp;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (ans.v[i][j].first >= inf)cout << "X 0 ";
else
cout << ans.v[i][j].first << " " << ans.v[i][j].second << " ";
}
cout << endl;
}
}
View Code