1001 Matrix
题意：
用[ 1 , n 2 ]的数填n ∗ n的矩阵，每个数字只能用一次，记a i表示第i行的最大值
S = a 1 , a 2 , . . . , a n ∩ 1 , 2 , . . . , n . S={a1,a2,...,an}∩{1,2,...,n}.
求∑ ∣ S ∣ \sum|S|∑∣S∣
思路：
考虑每一个数的贡献，比如1可以作为贡献的方案数就是n ∗ C n 2 − 1 n − 1。
其中组合数部分表示1作为该行的最小值出现，选择剩下的数的方案数；n表示该行可以出现在1 − n里任意一行。
最后还要乘n ! ∗ ( n 2 − n ) !。前者表示1所在行的所有数都可以全排列一遍，后者表示剩下的数可以全排列，对1的贡献是不影响的。
累加出1 − n的贡献，直接求或打表O ( 1 )
#include <bits/stdc++.h> using namespace std; #define ll long long const ll maxn = 2e7 + 5e6 + 7; const int mod = 998244353; ll qpow(ll a, ll b,ll p) { ll ans = 1; while(b) { if(b & 1) ans = ans * a % p; a = a * a % p; b >>= 1; } return ans; } ll fac[maxn]; void init() { fac[0] = 1; for(int i = 1; i < maxn; i++) { fac[i] = fac[i - 1] * i % mod; } } ll infac(ll x) { return qpow(x, mod - 2, mod); } ll C(ll n, ll m) { if(n < m) return 0; return fac[n] * infac(fac[m]) % mod * infac(fac[n - m]) % mod; } void solve() { ll n; scanf("%lld",&n); ll ans=n*fac[n]%mod*fac[n*n-n]%mod; ll sum=0; for(int i=1;i<=n;i++){ sum+=C(n*n-i,n-1); sum=sum%mod; } printf("%lld\n",ans*sum%mod); } int main() { init(); int t = 1; scanf("%d", &t); while(t--) { solve(); } return 0; }
1003 Vertex Deletion
1004 Lowbit
题意：
两种操作：
1.给区间[ l , r ]的所有数都加l o w b i t ( a i )
2.区间求和
思路：
如果一个区间的数都变成10000(二进制)这种形式，操作1就相当于区间乘法，维护懒标就好了。设一个标记f l a g表示该段区间都是1000这种形式，对于操作1的区间，看是否能转化成区间乘法
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll>PLL; typedef pair<int, int>PII; typedef pair<double, double>PDD; #define I_int ll inline ll read(){ll 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 * 10 + ch - '0';ch = getchar();}return x * f;} inline void write(ll x){if (x < 0) x = ~x + 1, putchar('-');if (x > 9) write(x / 10);putchar(x % 10 + '0');} #define read read() #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) const double PI=acos(-1.0); ll ksm(ll a,ll b,ll p){ ll res=1; a%=p; while(b){ //&运算当相应位上的数都是1时，该位取1，否则该为0。 if(b&1) res=1ll*res*a%p;//转换为ll型 a=1ll*a*a%p; b>>=1;//十进制下每除10整数位就退一位 } return res; } const int maxn=1e5+100; const ll mod=998244353; struct node{ int l,r,flag; ll sum,laz; }tr[maxn*4]; int n,m; ll a[maxn]; ll lowbit(ll x){return x&-x;} void pushup(int u){ tr[u].sum=(tr[u<<1].sum+tr[u<<1|1].sum)%mod; tr[u].flag=tr[u<<1].flag&tr[u<<1|1].flag; } void pushdown(int u){ if(tr[u].laz){ ll t=tr[u].laz; tr[u<<1].sum=(tr[u<<1].sum*ksm(2,t,mod))%mod; tr[u<<1|1].sum=(tr[u<<1|1].sum*ksm(2,t,mod))%mod; tr[u<<1].laz+=t; tr[u<<1|1].laz+=t; tr[u].laz=0; } } void build(int u,int l,int r){ tr[u].l=l,tr[u].r=r; tr[u].flag=tr[u].laz=tr[u].sum=0; if(l==r){ tr[u].flag=tr[u].laz=0; tr[u].sum=a[l]; if(a[l]==lowbit(a[l])) tr[u].flag=1; return ; } int mid=(l+r)/2; build(u<<1,l,mid); build(u<<1|1,mid+1,r); pushup(u); } void update(int u,int l,int r,int ql,int qr){ if(tr[u].flag&&l>=ql&&r<=qr){ tr[u].laz++; tr[u].sum=(tr[u].sum*2)%mod; return ; } if(l==r){ ll tmp=lowbit(a[l]); a[l]+=tmp; tr[u].sum+=tmp; if(tr[u].sum==lowbit(tr[u].sum)){ tr[u].flag=1; } return ; } pushdown(u); int mid=(l+r)/2; if(ql<=mid) update(u<<1,l,mid,ql,qr); if(qr>mid) update(u<<1|1,mid+1,r,ql,qr); tr[u].sum=(tr[u<<1].sum+tr[u<<1|1].sum)%mod; tr[u].flag=tr[u<<1].flag&tr[u<<1|1].flag; } ll query(int u,int l,int r,int ql,int qr){ if(l>=ql&&r<=qr){return tr[u].sum;} pushdown(u); ll ans=0; int mid=(l+r)/2; if(ql<=mid) ans=(ans+query(u<<1,l,mid,ql,qr))%mod; if(qr>mid) ans=(ans+query(u<<1|1,mid+1,r,ql,qr))%mod; return ans; } int main(){ int _;cin>>_; while(_--){ n=read; rep(i,1,n) a[i]=read; build(1,1,n); m=read; while(m--){ int op=read,l=read,r=read; if(op==1) update(1,1,n,l,r); else printf("%lld\n",query(1,1,n,l,r)); } } return 0; }
1005 Easy Math Problem
思维构造
int main() { int t=1; scanf("%d",&t); while(t--){ ll n; scanf("%lld",&n); cout<<6*n<<" "<<3<<endl; cout<<n<<" "<<2*n<<" "<<3*n<<endl; } return 0; }
1009 Takeaway
阅读理解题
int a[]={0,7,27,41,49,63,78,108}; int main(){ closeSync; int _=read; while(_--){ int n=read,sum=0; rep(i,1,n){ int x=read; sum+=a[x]; } int ans=0; if(sum>=120) ans+=50; if(sum<120&&sum>=89) ans+=30; if(sum<89&&sum>=69) ans+=15; cout<<sum-ans<<endl; } return 0; }
1010 Transform
题意：
三维空间里给出一个点和一个向量，问点围绕向量旋转t度后，输出z坐标大的点
思路：
板子题
代码：
const double PI=acos(-1.0); //定义返回结构体 struct Point3f { Point3f(double _x, double _y, double _z) { x = _x; y = _y; z = _z; } double x; double y; double z; }; Point3f cul(double old_x, double old_y, double old_z, double vx, double vy, double vz, double theta) { double r = theta * PI / 180; double c = cos(r); double s = sin(r); double new_x = (vx*vx*(1 - c) + c) * old_x + (vx*vy*(1 - c) - vz*s) * old_y + (vx*vz*(1 - c) + vy*s) * old_z; double new_y = (vy*vx*(1 - c) + vz*s) * old_x + (vy*vy*(1 - c) + c) * old_y + (vy*vz*(1 - c) - vx*s) * old_z; double new_z = (vx*vz*(1 - c) - vy*s) * old_x + (vy*vz*(1 - c) + vx*s) * old_y + (vz*vz*(1 - c) + c) * old_z; return Point3f(new_x, new_y, new_z); } int main(){ int _=read; while(_--){ double x1,y1,z1,x2,y2,z2,t; cin>>x1>>y1>>z1>>x2>>y2>>z2>>t; double sum=sqrt(x1*x1+y1*y1+z1*z1); x1/=sum,y1/=sum,z1/=sum; Point3f t1=cul(x2,y2,z2,x1,y1,z1,t); Point3f t2=cul(x2,y2,z2,x1,y1,z1,-1*t); if(t1.z>t2.z) printf("%.6f %.6f %.6f\n",t1.x,t1.y,t1.z); else printf("%.6f %.6f %.6f\n",t2.x,t2.y,t2.z); } return 0; }
1011 City
题意：
给出一个图，每次询问给出x，每次将边权< x
思路：
按照边权从大到小排序，依次连边，每次连边产生的贡献是s i z [ u ] ∗ s i z [ v ]
代码：
const int maxn=2e5+10,inf=0x3f3f3f3f; const double eps=1e-5; int n,m,q; struct node{ int u,v,w; }edge[maxn]; bool cmp(node a,node b){ return a.w>b.w; } struct ask{ int id,w; }qask[maxn]; bool cmp1(ask a,ask b){ return a.w>b.w; } ll root[maxn],siz[maxn],ans[maxn]; int Find(int x){ if(x!=root[x]) root[x]=Find(root[x]); return root[x]; } int main(){ closeSync; int _;cin>>_; while(_--){ cin>>n>>m>>q; rep(i,1,m){ cin>>edge[i].u>>edge[i].v>>edge[i].w; } sort(edge+1,edge+1+m,cmp); rep(i,1,n) root[i]=i,siz[i]=1; rep(i,1,q){ cin>>qask[i].w;qask[i].id=i; } sort(qask+1,qask+1+q,cmp1); ll now=1,sum=0; for(int i=1;i<=q;i++){ while(edge[now].w>=qask[i].w){ int u=edge[now].u,v=edge[now].v; int fu=Find(u),fv=Find(v); if(fu!=fv){ sum+=siz[fu]*siz[fv]; root[fu]=fv; siz[fv]+=siz[fu]; } now++; } ans[qask[i].id]=sum; } rep(i,1,q) cout<<ans[i]<<endl; } return 0; }
1013 Master of Shuangpin
思路：
模拟。
代码：
const int maxn=500005,inf=0x3f3f3f3f; const double eps=1e-5; map<string,string>mp; void init(){ mp["q"] = "q"; mp["iu"] = "q"; mp["w"] = "w"; mp["ei"] = "w"; mp["e"] = "e"; mp["r"] = "r"; mp["uan"] = "r"; mp["t"] = "t"; mp["ue"] ="t"; mp["y"] = "y"; mp["un"] = "y";// mp["u"] = "u"; mp["sh"] = "u"; mp["i"] = "i"; mp["ch"] = "i"; mp["o"] = "o"; mp["uo"] = "o"; mp["p"] = "p"; mp["ie"] = "p"; mp["a"] ="a"; mp["s"] = "s"; mp["ong"] = "s"; mp["iong"] = "s"; mp["d"] = "d"; mp["ai"] = "d"; mp["f"] = "f"; mp["en"] = "f"; mp["g"] = "g"; mp["eng"] = "g"; mp["h"] = "h"; mp["ang"] = "h"; mp["j"] = "j"; mp["an"] = "j"; mp["k"] = "k"; mp["uai"] = "k"; mp["ing"] = "k"; mp["l"] = "l"; mp["uang"] = "l"; mp["iang"] = "l"; mp["z"] = "z"; mp["ou"] = "z"; mp["x"] = "x"; mp["ia"] = "x"; mp["ua"] = "x"; mp["c"] = "c"; mp["ao"] = "c"; mp["v"] = "v"; mp["ui"] = "v"; mp["zh"] = "v"; mp["b"] = "b"; mp["in"] = "b"; mp["n"] = "n"; mp["iao"] = "n"; mp["m"] = "m"; mp["ian"] = "m"; } int main(){ init(); string s; while(getline(cin,s)){ stringstream ss; ss<<s; string tt=""; while(ss>>s){ if(s.size()==1) tt=tt+s+s+" ";//cout<<s<<s<<" "; else if(s.size()==2) tt=tt+s+" ";//cout<<s<<" "; else{ if(mp.count(s)){ tt=tt+s[0]+mp[s]+" "; // cout<<s[0]<<mp[s]<<" "; continue; } string res=""; bool flag=0; for(int i=1;i<s.size();i++){ string s1=s.substr(0,i); string s2=s.substr(i,s.size()-1); //cout<<s1<<" "<<s2<<endl; if(mp.count(s1)&&mp.count(s2)){ flag=1; res=mp[s1]+mp[s2]; break; } } tt=tt+res+" "; // cout<<res<<" "; } } tt=tt.substr(0,tt.size()-1); cout<<tt<<endl; } return 0; }
