題目連結：http://acm.hdu.edu.cn/contests/contest_show.php?cid=869
1001 . ^&^
位運算簽到題，輸出a，b與的結果，如果為0，輸出lowbit最小的。
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) x&-x
typedef long long ll;
int main()
{
long long a,b;
int t;
cin>>t;
while(t --)
{
cin>>a>>b;
long long c = (a&b);
if( c == 0)
{
ll bb = lowbit(b);
ll aa = lowbit(a);
c= min(aa,bb);
}
cout<<c<<endl;
}
}
1002 array
對于1操作可以發現，1操作過的點都是解集中的可行點。是以對于1操作過的全部計入一個set。
對于2操作的詢問，我們可以建立主席樹和靜态第k大一樣，維護的是區間包含數字個數，題目保證所有數字不相同了，是以隻要改一下查詢函數就行了，查詢的的時候先判斷區間的長度是否等于區間記錄的sum，如果相等說明這個區間已經沒有可以用的點了，傳回0，再查左區間有沒有可用的點，如果有就去左區間，如果沒有就去遞歸右區間。
#include <bits/stdc++.h>
using namespace std;
const int MAXN =1e5 + 5;
struct Tree{
int l,r,sum;
}T[MAXN*30];
int rt[MAXN],a[MAXN],cnt,sz;
void init()
{
cnt=0;
T[cnt].l=T[cnt].r=T[cnt].sum=0;
rt[cnt]=0;
memset(a,0,sizeof(a));
}
void Update(int l,int r,int &x,int y,int pos)
{
T[++cnt]=T[y];T[cnt].sum++;x=cnt;
if(l==r)return ;
int mid = (l+r)/2;
if(mid>=pos){
Update(l,mid,T[x].l,T[y].l,pos);
}
else
Update(mid+1,r,T[x].r,T[y].r,pos);
}
int query(int l,int r,int x,int y,int k)
{
if(T[y].sum-T[x].sum==r-l+1)
return 0;
if(l==r){
return l;
}
int mid = (l + r)/2;
int sum = T[T[y].l].sum-T[T[x].l].sum;
int num = mid-l+1;
if(k <= mid)
{
int tmp = query(l,mid,T[x].l,T[y].l,k);
if(!tmp)
return query(mid+1,r,T[x].r,T[y].r,k);
return tmp;
}
else
return query(mid+1,r,T[x].r,T[y].r,k);
}
set<int>s;
int main()
{
int t;
scanf("%d",&t);
while(t --)
{
int n,m;
scanf("%d%d",&n,&m);
s.clear();
cnt = 0;
memset(rt,0,sizeof(rt));
for(int i = 1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++){
Update(1,n,rt[i],rt[i-1],a[i]);
}
int tmp = 0;
for(int i = 1;i<=m;i++)
{
int op,r,k;
scanf("%d",&op);
if(op == 1)
{
scanf("%d",&r);
r ^= tmp;
s.insert(a[r]);
}
else
{
scanf("%d%d",&r,&k);
r^= tmp,k^=tmp;
int ans1 = query(1,n,rt[0],rt[r],k);
if(!ans1)ans1 = n + 1;
int ans2 = n + 1;
set<int>::iterator it = s.lower_bound(k);
if(it != s.end())ans2 = *it;
tmp = min(ans1,ans2);
printf("%d\n",tmp);
}
}
}
return 0;
}
1003
據說是NOI原題，字尾數組+主席樹+rmq ???賽場沒做出來，打算學一下SA.
1004 path
題目思路：考慮bfs，先把全部的邊入隊列，然後再往外bfs。每次取隊首，然後接上一個點，再塞回去，把查詢離線，然後記錄前max(k)取隊首，就可以O（1）通路了。
直接優先隊列模拟的話，會被菊花圖卡時間和空間，是以要加一個優化，優先隊列改用set，保證每次set裡最多隻有max(k)個元素。（比賽時演了戲，I self-criticism three thousand !!!）
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define per(i,a,b) for(ll i=a;i>=b;i--)
#define ll long long
const ll MAXN = 5e4+5;
const ll MOD = 1e9+7;
struct node{
ll x,y;
ll val;
bool operator <(const node &r)const{
return val<r.val;
}
}a,b;
multiset<node>s;
struct nod{
ll to,val;
}p;
vector<nod>v[MAXN],g[MAXN];
ll ans[MAXN],c[MAXN];
bool cmp(nod a,nod b){
return a.val<b.val;
}
int main()
{
ll t,n,m,Q,u,V,w;
scanf("%lld",&t);
while(t--){
ll maxx=0;
scanf("%lld%lld%lld",&n,&m,&Q);
s.clear();
rep(i,1,n)v[i].clear();
while(m--){
scanf("%lld%lld%lld",&u,&V,&w);
p.to=V,p.val=w;
v[u].push_back(p);
a.x=u,a.y=V;
a.val=w;
s.insert(a);
}
rep(i,1,n)sort(v[i].begin(),v[i].end(),cmp);
rep(i,1,Q){
scanf("%lld",&c[i]);
maxx=max(maxx,c[i]);
}
ll pos=0;
multiset<node>::iterator it;
while(!s.empty()){
a=*s.begin();
s.erase(s.begin());
ans[++pos]=a.val;
if(pos==maxx)break;
int len=v[a.y].size();
rep(i,0,len-1){
b=a;
b.y=v[a.y][i].to;
b.val+=v[a.y][i].val;
if(s.size()>maxx-pos){
it=s.end();
it--;
if((*it).val>b.val){
s.erase(it);
s.insert(b);
}
else break;
}
else{
s.insert(b);
}
}
}
rep(i,1,Q){
printf("%lld\n",ans[c[i]]);
}
}
return 0;
}
1006 Shuffle Card
簽到題。
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) x&-x
typedef long long ll;
const int maxn = 1e5 + 5;
int flag[maxn];
typedef pair<int,int> pii;
deque<pii>q;
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
memset(flag,0,sizeof(flag));
q.clear();
for(int i = 1;i<=n;i++)
{
int x;
scanf("%d",&x);
pii tmp = (pii){x,0};
q.push_back(tmp);
}
for(int i = 1;i<=m;i++)
{
int x;
scanf("%d",&x);
flag[x]++;
pii tmp = (pii){x,flag[x]};
q.push_front(tmp);
}
while(!q.empty())
{
pii tmp = q.front();
q.pop_front();
if(tmp.second == flag[tmp.first])
{
printf("%d ",tmp.first);
}
}
}
return 0;
}
1007 Windows Of CCPC
簽到題，代碼略了。
1008 Fishing Master
挺好的一個貪心題，首先我們第一次捕魚和所有的炖魚時間都要計入答案，再煮魚的時候我們可以去選擇釣魚，但是我們最多釣a[i]/k條魚，此時我們有一個選擇就是，要不要多花k-（a[i]%k）的時間去多釣一條魚，仔細思考一下，就是如果我們随後不缺魚可炖，肯定不需要多花這個時間，但是萬一我們後邊缺魚了，那麼我們必須多花這個時間，是以，我們把這個時間入一個優先隊列，如果後邊需要煮魚但是手裡魚數量不夠了，此時必須去前邊多花一點時間換一條魚，取隊首就好了。
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define per(i,a,b) for(ll i=a;i>=b;i--)
#define ll long long
const ll MAXN = 1e5+5;
const ll MOD = 1e9+7;
ll a[MAXN];
priority_queue<ll,vector<ll>,greater<ll> >q;
bool cmp(ll a,ll b){
return a>b;
}
int main()
{
ll t,n,k;
scanf("%lld",&t);
while(t--){
while(!q.empty())q.pop();
scanf("%lld%lld",&n,&k);
rep(i,1,n)scanf("%lld",&a[i]);
sort(a+1,a+n+1,cmp);
ll ans=k,num=1;
rep(i,1,n){
ans+=a[i];
if(num>=i){
num+=a[i]/k;
q.push(k-(a[i]%k));
continue;
}
if(q.empty())ans+=k;
else{
ans+=q.top();
q.pop();
}
num+=a[i]/k;
q.push(k-(a[i]%k));
}
printf("%lld\n",ans);
}
return 0;
}
![杭電第十場 題解進階題[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)