本蒟蒻這次只過了三題 賽后學習了一下出題人巨佬的標碼(碼風比我好多了 貼的代碼有些是仿出題人)
現在將自己的理解寫下來與大家分享
A
這個題一分析就是每個數字都會與所有數字&一下 (a&a=a)
&字操作是二進制同位都為一才為一 這時解法就變成統計每個二進制位上1的次數
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 1e5;
const ll maxm = 30;
ll res;
ll arr[maxn + 5], n, cnt[maxm + 5];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i)scanf("%d", &arr[i]);
for (int i = 1; i <= n; ++i)
for (int j = 0; j < 30; ++j)
if (arr[i] & (1 << j))cnt[j] += 1;///各位上1的個數
for (int i = 0; i < 30; ++i)res += cnt[i] * cnt[i] * (1 << i);
printf("%lld\n", res);
return 0;
}
|
B
簡單的n2列舉 分析一下可以知道每條邊都用了n-2次
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n,ans;
ll mod=998244353;
struct P
{
ll x,y;
}a[110];
ll len(P m,P n)
{
return abs(m.x-n.x)+abs(m.y-n.y);
}
int main()
{
scanf("%lld",&n);
for(int i=1;i<=n;++i)scanf("%lld%lld",&a[i].x,&a[i].y);
for(int i=1;i<=n;++i)
{
for(int j=i+1;j<=n;++j)
{
ans+=(len(a[i],a[j])*(n-2))%mod;
}
}
cout<<ans%mod<<endl;
return 0;
}
|
C
這是一個比較基礎的dp方程的進階 從n個物品中選k個
dp[i][j]=dp[i-1][j]+dp[i-1][j-1]
i表示到第幾個字符了 j是用了幾個字符
dp[i-1][j]是不用這個新加的 dp[i-1][j-1]是用這個新加的
這題的關鍵點是我們這樣計算重復了多少字符（本質不同的解釋）
其實仔細一想 我們重復計算就是相當于把 輸出前面出現的那個符號在那里又多算了一次
多了哪一部分 這個重復符號上次出現的位置的dp值
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 1000;
const ll mod = 1e9 + 7;
ll dp[maxn + 5][maxn + 5];
ll n, k, pre[maxn + 5];///pre記錄上次同一個字符的出現位置
char s[maxn + 5];
int main()
{
scanf("%d %d", &n, &k);
scanf("%s", s + 1);
dp[0][0] = 1;///n中選0個為1種情況
for (int i = 1; i <= n; ++i) {
dp[i][0] = 1;
for (int j = 1; j <= i; ++j) {
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
if (pre[s[i] - 'a'])dp[i][j] -= dp[pre[s[i] - 'a'] - 1][j - 1];
dp[i][j] %= mod;
}
pre[s[i] - 'a'] = i;
}
ll res = dp[n][k];
if (res < 0)res += mod;
printf("%lld\n", res);
return 0;
}
|
D
這題由于蒟蒻（我）追求夢想用n2列舉過了 但賽后還是寫了一下正解方程（n列舉應該可以過）
寫這題你需要一個 擴展歐幾里得模板（能判斷是否有整數解） 然后列舉一個數就把題目變成了一個模板題了 前面是n2列舉 后面大概是正解
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b,c,k,minl;
int main()
{
cin>>a>>b>>c>>k;
minl=min(a,min(b,c));
ll s=k/minl;
for(int i=1;i<=s;++i)
{
for(int j=1;j<=s;++j)
{
ll z1=k-a*i-b*j;
ll z2=k-b*i-c*j;
ll z3=k-a*i-c*j;
if(z1%c==0){cout<<i<<" "<<j<<" "<<z1/c;return 0;}
if(z2%a==0){cout<<z2/a<<" "<<i<<" "<<j;return 0;}
if(z3%b==0){cout<<i<<" "<<z3/b<<" "<<j;return 0;}
}
}
return 0;
}
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b,c,k;
void exgcd(ll a,ll b,ll&x,ll&y)
{
if(b==0)
{
x=1;
y=0;
return;
}
exgcd(b,a%b,x,y);
ll t=x;
x=y;
y=t-(a/b)*y;
}
ll gcd(ll a,ll b){
return b==0?a:gcd(b,a%b);
}
int main()
{
scanf("%lld%lld%lld%lld",&a,&b,&c,&k);
for(ll i=0;i<=k/c;i++){
ll d=k-i*c;
ll x,y;
exgcd(a,b,x,y);
ll e=gcd(a,b);
if(d%e!=0) continue;///有無解
ll n=d/e;
ll m=b/e;
x*=n;y*=n;
x=(x%m+m)%m;
y=(d-x*a)/b;///有無整數解
if(x>=0&&y>=0){
printf("%lld %lld %lld",x,y,i);
return 0;
}
}
return 0;
}
|
F
這題作為正在學習計算幾何的蒟蒻（我） 那肯定是要學習的
做這題的關鍵是要注意畫圖才能理解 代碼里大部分有注釋
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 |
#include<bits/stdc++.h>
#define lowbit(x) x&(-x)
#define ll long long
using namespace std;
typedef pair<int,int> pii;
const int maxn=1e5+7;
const int pi=acos(-1.0);
const double eps=1e-9;
int read()///快讀
{
int x=0,f=1;char s=getchar();
for( ;!isdigit(s);s=='-' && (f=-1),s=getchar());
for( ;isdigit(s);x=x*10+s-48,s=getchar());
return x*f;
}
struct point
{
int x,y,tag;
point( ) { x=y=tag=0; }
point( ll _x,ll _y )
{
x=_x,y=_y;
}
bool operator==( const point& rhs ) const {
return x==rhs.x && y==rhs.y;
}
point operator -(const point &rhs ) const {
return point(x-rhs.x,y-rhs.y);
}
point operator+( const point &rhs ) const {
return point(x+rhs.x,y+rhs.y);
}
ll operator * ( const point &rhs ) const { /// 叉積
return 1ll*x*rhs.y-1ll*y*rhs.x;
}
ll dot( const point &rhs ) const { /// 點積
return 1ll*x+rhs.x+1ll*y*rhs.y;
}
void get() { x=read(),y=read(); }
}O,p[maxn],w1[maxn],w2[maxn],A,B;
int n,m1,m2;
inline bool cmpA( point a,point b ) { return (a-A)*(b-A)>0; }
inline bool cmpB( point a,point b ) { return (a-B)*(b-B)>0; }
int c[maxn];
ll ans=0;
void add( int x ) { while( x<n ) c[x]++,x+=lowbit(x); }
int query( int x ,int tt=0 ) { while( x ) tt+=c[x],x-=lowbit(x);return tt;}
void solve( point *t,int m )
{
sort(t+1,t+1+m,cmpA);///以A點極角排序
ans+=(1ll*m*(m-1))>>1;///先假設所有點對都能與線段相交
for( int i=1;i<=m;i++ ) t[i].tag=i;
sort(t+1,t+m+1,cmpB);///以B點極角排序
memset(c,0,sizeof(c));
for( int i=1;i<=m;i++ )///減去不能與線段相交的點對
{
///這里假設線段點為P、Q 選出來的點對為 A、B 在畫圖程序中發現
///選出來的能交的點對 B點要以P排序在A前面而且以Q排序也要在A前面
///不是就減去 以樹狀陣列解決這個區間問題
ans-=query(t[i].tag);
add(t[i].tag);
}
}
int main()
{
n=read(),A.get(),B.get();
for( int i=1;i<=n;i++ ) p[i].get();
for( int i=1;i<=n;i++ )
{
if( (A-p[i])*(B-p[i])>0ll ) w1[++m1]=p[i];///利用叉積把點分為線段上下兩部分
else w2[++m2]=p[i];
}
solve(w1,m1);///第一種情況 兩個點在同一側
solve(w2,m2);
ans+=1ll*m1*m2;///第二種情況 兩個點在不同側 還是一樣先假設所有點對都能與線段相交
sort(w1+1,w1+m1+1,cmpA);///一樣 以A點極角排序
sort(w2+1,w2+m2+1,cmpA);
for( int i=1,bas=1;i<=m1;i++ )///減去不能與線段相交的點對
{
///i 上側 bas 下側
///畫圖分析
while( bas<=m2 && (w1[i]-A)*(w2[bas]-A)>0 ) ++bas;///叉積判斷
ans-=bas-1;
}
sort(w1+1,w1+m1+1,cmpB);///以B點極角排序
sort(w2+1,w2+m2+1,cmpB);
for( int i=1,bas=1;i<=m2;i++ )
{
///一樣
while( bas<=m1 && (w2[i]-B)*(w1[bas]-B)>0 ) ++bas;
ans-=bas-1;
}
printf("%lld\n",ans);
return 0;
}
|
e題的題解可能在我大佬隊友寫完后貼出來（這個方向我是真不會）.....
看到最后的彩蛋 推薦純音樂 Like Sunday,Like Rain ^-^
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/67588.html
標籤：其他
下一篇：求阿里云邀請碼